Guarantees for Alternating Least Squares in Overparameterized Tensor Decompositions
Authors: Dionysis Arvanitakis
Vaidehi Srinivas
Aravindan Vijayaraghavan
Venue: NeurIPS 2025 spotlight ()
Keywords: tensor decomposition
overparameterization
alternating least squares
optimization
iterative methods
Primary area: optimization
TL;DR: We prove that ALS with overparameterized rank $k=r^2$ achieves global convergence for decomposing rank $r$ tensors

Abstract: Tensor decomposition is a canonical non-convex optimization problem that is computationally challenging, and yet important due to applications in factor analysis and parameter estimation of latent variable models. In practice, scalable iterative methods, particularly Alternating Least Squares (ALS), remain the workhorse for tensor decomposition despite the lack of global convergence guarantees. A popular approach to tackle challenging non-convex optimization problems is overparameterization--- on input an $n \times n \times n$ tensor of rank $r$, the algorithm can output a decomposition of potentially rank $k$ (potentially larger than $r$).  On the theoretical side, overparameterization for iterative methods is challenging to reason about and requires new techniques.  The work of Wang et al., (NeurIPS 2020) makes progress by showing that a variant of gradient descent globally converges when overparameterized to $k=O(r^{7.5} \log n)$.  Our main result shows that overparameterization provably enables global convergence of ALS: on input a third order $n \times n \times n$ tensor with a decomposition of rank $r \ll n$, ALS overparameterized with rank $k=O(r^2)$ achieves global convergence with high probability under random initialization. Moreover our analysis also gives guarantees for the more general low-rank approximation problem. The analysis introduces new techniques for understanding iterative methods in the overparameterized regime based on new matrix anticoncentration arguments.

Guarantees for Alternating Least Squares in Overparameterized Tensor Decomposition
Dionysis Arvanitakis
Vaidehi Srinivas
Department of Computer Science Northwestern University Evanston, IL 60208
Department of Computer Science
Northwestern University
Evanston, IL 60208
di oiaavaauu. hot.rrasttttoootttteteeeeeeeet
vaideh @u wow.hrestene..edeee
Aravindan Vijayaraghavan Department of Computer Science
Northwestern University Evanston, IL 60208
aravindv@hootthwessee.c edu
Abstract
Tensor decomposition is canonical non-convex optimization problem that is computationally challenging, and yet important due to applications factor analysis and parameter estimation of latent variable models. In practice, scal- able iterative methods, particularly Alternating Least Squares (ALS), remain the workhorse for tensor decomposition despite the lack of global convergence guaran- tees. A popular approach to tackle challenging non-convex optimization problems is overparamettrriztionn can output a decomposition of potentially rank (potentially larger than r). On the theoretical side, overparameterization for iterative methods is challenging reason about and requires new techniques. The work of Wang et al., (NeurIPS 2020) makes progress by showing that variant of gradient descent globally converges when overparameterized to k (rr log Our main result shows that overpa- rameterization provably enables global convergence of ALS: on input a third order n X n X n tensor with a decomposition of rank r < n. ALS overparameterized with rank = Orr²) achieves global convergence with high probability under random initialization. Moreover our analysis also gives guarantees for the more general low-rank approximation problem. The analysis introduces new techniques for understanding iterative methods in the overparameterized regime based on new matrix anticoncentration arguments.
input
tensor of rank r, the algorithm
Introduction
Iterative heuristics like alternating least squares (ALS), alternate minimization, and gradient descent are the workhorse for many computational tasks in machine learning and high-dimensional data analysis. Their simplicity, scalability and empirical success have led their widespread use, even for highly non-convex problems. Yet rigorous guarantees have been hard to establish due to the non-convex nature these problems.
Tensor decomposition a prime example of a well-studied non-convex problem where there is a disconnect between the practical performance of iterative heuristics and known theoretical guarantees. We are given third-order tensor E R and the goal is to decompose the tensor as a sum of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

a few rank-1 1 tensors when possible, i.e.
T 2, & y1 8 2,
Σ
where the {az & yi ② : {24, Mi, 2 : [k]] E R" are called the factors of the decomposition. This is sometimes called the CP decomposition of the tensor, and is an important tool in factor analysis and parameter estimation
} are the rank-1 terms of the decomposition, and the vectors
of many latent variable models in machine learning [see e.g., K B09 Moi JGKA19]. Finding the smallest r for which rank-r decomposition of ' exists is NP-hard in the worst case [Hás90] HI.K3 Algorithmic guarantees are known under additional genericity or smoothed analysis assumptions for more sophisticated but less scalable algorithms like simultaneous diagonalization and other spectral
methods [Har72 [RA93], algebraic methods [DLCC07 and the sum-of-squares hierarchy (BKSI5)
(see Vij20] for more detailed comparisons).
The most popular algorithms in practice are iterative methods for the optimization problem given by the least squares objective
k 24
min (1 |
(1)
In particular, the Alternating Least Squares (ALS) algorithm an iterative algorithm that alternately R", while keeping the rest of them (y1..... yk updates one of variables, say 21,..., Fk and 21,..., 25.) fixed. Note that each update step is least squares problem (e.g.. in the variables Ti. .i....,221 24) when the remaining variables are fixed (see Section more detailed description of the algorithm). The optimization landscape of ([ is highly non-convex, and such iterative algorithms can potentially converge bad local optima. This has
inspired new variants of ALS like the Orthogonalized ALS algorithm of [SV17), that come with rigorous guarantees under strong assumptions like orthogonality or incoherence of the factors. Yet, the ALS algorithm remains the most popular method for tensor decompositions in practice, despite our poor understanding of when ALS succeeds [KB09 BK25).
Overparameterization has recently emerged as a powerful approach to mitigating non-con non-convexity. Introducing more parameters than those of the boound-truth model often improves optimization dynamics in practice, even in complex settings like training deep neural networks. In our setting, the given tensor T has rank decomposition of the form T E 0g & by ct, and the goal is to find a decomposition of potentially larger rank k.
It is challenging to reason about overparameterization with iterative methods for tensor decomposition. Existing approaches based on lazy training and standard mean-field analysis requires an overpa- rameterization of rank that depends polynomially or even exponentially on the ambient dimension. Surprisingly, the work of [WLL=20 makes progress by showing global convergence for a variant of gradient descent with moderate overparameterizztion of k O(r log n) that is nearly independent of the ambient dimension n. The main question we address in this paper is:
Question. Does ALS admit a polynomial time global convergence guarantee with moderate overpa- rameterization (a function of r and not n)?
Our main result answers this question in the affirmative. Coneretely, our main contributions are the following:
We prove that the ALS algorithm on a tensor with mildly conditioned rank-r decom- position I when overparameterized with & = O(r2) and with random initialization of
{(x;, Bi: 2;) : [r]], converges with high probability to a global minimum (i.c., objective value 0).
We also provide rigorous guarantees for ALS under overparameterizzaton for the more general low-rank approximation problem
OPT,-
min ((ree)
T
Σ Z
(2)
1=1
By midly conditioned mean that the condition numbers of factor matrices are bounded by (oly(r)

---

We prove that ALS when overparameterized with k = Orr²) and initialized randomly, finds solution whose objective value competitive with the OPT, up to a multiplicative factor that is polynomial in only (and independent of n).
For both our results, a moderate overparameterization of h: = Orr²) suffices. We suspect it may be challenging improve the amount of overparameteriration necessary. We remark that even for more computationally-intenn
algorithms based on spectral methods, the best polynomial time guarantees require an overparamettriiztion of k O [BVV14 SWZI9]. We leave it as a direction for future work to investigate whether one can prove better upper or lower bounds on the amount of overparameterizatioo necessary to recover a provable guarantee for ALS.
Recent work has developed a few different techniques for analyzing iterative methods with overparam- eterization. Techniques based the lazy training approach argue that when the model is sufficiently overpurameterized. the optimization problem is locally convex and the method will converge to a good solution near the initialization [COB19] Lazz training analyses incur overparameterization that is polynomial in the ambient dimension n, which can be very large compared to the rank r.
The work of [WWL makes progress by instead adopting the framework of mean field analysis. While previous work that introduced this technique analyzes problems in the case of very large, or even infinite overparameterizatten [MNN8 [WWL 201 was able to show global convergence for a variant of gradient descent with only moderate overparameterriztion of k = O log n 2 achieving an exponentially better dependence
than lazy training analyses for small
Our work develops an analysis that is significantly different from previous approaches, based on new matrix anticoncentration statements. At high level, we observe that if the iterates X, Y, Z are sufficiently random and in the span of the components of the true tensor, then due to overpa- rameterization they will form a basis for an appropriate space related to the components. If this occurs, then the next iteration of ALS will find a near-exact solution and converge. At initialization, X,Y, Z are independently fully random. However, they are random in the ambient space, and not restricted to the subspace of interest. The first iteration of ALS should in fact update X, Y, Z to be within the correct space. However, the updated X, Y, Z now exhibit significant dependencies on each other. Our analysis shows that despite this, the updated X, Y, Z are still random enough to form the appropriate basis. Thus, the crux of our argument is in showing that this iteration preserves enough randomness from the initialization. Quantitatively, this requires arguing about the least singular value of various structured random matrices that arise in the algorithm, along with careful matrix perturbation analyses. Our techniques are applied to a version of ALS that updates all the factor matrices in parallel. Similar guarantees, based on these techniques, for the standard ALS will appear in the arxiv version of the paper.
1.1 Related Work
We now describe related work on tensor decompositions and overparametttiizatoo,, and place our work in the context of these prior works.
Tensor decomposition has rich history going back to least [0 Har72).
This decomposition into a sum of rank-one tensors is also referred to as CP decomposition or PARAFAC decomposition.
See also BK9 for other decomposition notions for tensors including Tucker decompositions. There are several iterative algorithms that are popular in practice like alternating least squares, alternate minimization, gradient descent and tensor power method [see KB09 AGH JGKA19 for more details]. In particular, the ALS algorithm was first introduced by Har CC70). and has been the workhorse algorithm for tensor decomposition in practice [BK25]. While ALS is popular for its efficiency and steps towards understanding convergence of the iterates have been made 2Usc12 WC14], we do not have a good understanding of when it converges to a global optimum solution.
The two results on tensor decompositions that is most relevant to our work are the work of Sharan and Valiant [SV17] who introduced and gave guarantees for an orthogonalized version of ALSS and the work of Wang, Wu, Lee, Ma and Ge WWWL++00 on analyzing gradient descent in the overparameterized regime.
For order-E tensors the bound on overparameterizaaton is 2,52.5 log(n)). Our work only focuses on the order-3 case.
3

---

Comparison to the Orthogonalized ALS algorithm. The work of Sharan and Valiant [SV17] introduced: a variant of the ALS algorithm that orthogonalizes the factors in each step, in addition to the ALS update. As described in [SV17] this allows the ALS algorithm to avoid issues where multiple components of the decomposition capture the same factor of the tensor, when the rank-1 terms have different magnitudes. Their work also proves guarantees under the assumption that the factors {a, : E [r]] of the decomposition are orthogonal or incoherent. The decomposition computed by the algorithm is not overparameterized i.e., k r. However, the algorithm is more suited for settings where the target decomposition has near-orthogonal factors. Our analysis is for the ALS algorithm in the overparameterized regime. We do not make incoherence or orthogonality assumptions on the factors; we just need mild conditioning of the factor matrix (condition number that is polynomial in r). One can interpret results proving that in the overparameterized setting, ALS does not face some fo the earlier issues pointed out in [V17].
Overparameterized tensor decompositions using iterative algorithms. The work of WWL, 20 analyzed variant of gradient descent in the overparameterized regime of tensor decompositions. Their techniques were able to go beyond lazy-training analyses, and the standard mean-fiel field analysis bounds that require overparameterization of polynomial even exponential in the ambient dimension n. They were surprisingly able to provide guarantees for overparameterizedd rank h that is almost independent of the ambient dimension. Concretely, their guarantees hold for third-order tensors when the overparameterization is A = O(r log n):: for general order-& tensors they need k = Orr2.2 logn) In this work, we instead analyze ALS in the overparameterized regime. We can get guarantees for smaller overparameterized rank k O(r²). Moreover, also approximation guarantees for overparameterizee ALS even when the tensor is not exactly of rank r. We get guarantees for the more general low-rank approximation problem that incurs loss that is within multiplicative factor (depending polynomially only on r, and independent of k) of the optimum value. To the best of our knowledge, we are unaware of any such guarantees for gradient descent and other iterative algorithms.
Analysis of other iterative algorithms for tensor decompositions. There are several other works that try to provide guarantees for iterative methods including alternating minimization, the tensor power method, and other gradient descent based algorithms. The work of [AGH* 14] analyzes the tensor power method, and provides guarantees that specialized to the setting when the factors also
are orthogonal or near orthogonal [AGH* + 14, AGJ14 AG]17) The works of analyze a variant of the alternating minimization algorithm, and provides convergence guarantees under nearby initialization. These works are not in the overparameterized regime (k- = r). They find components one at a time but either require stronger assumptions, or provide local convergence guarantees. Finally, it is known that for certain matrix factorization problems and special settings of tensor decomposition (c.g., orthogonal factors), the non-convex optimization landscape is benign i.c.. it does not have any local optima that are not globally optimal [Ma21]. However, the general tensor decomposition is highly non-convex with bad local minima as shown (WWL+
Other tensor decomposition algorithms. Theoretical guarantees have been established for the simultaneuous diagonalization algorithm [Har72, [RA93] Moi1&] and its variants, algebraic meth- ods [DLCC07 [LV23] Koi24 KMW24], sum- -um-of-squares algorithms [BKS15 15 HSSS16 MSS16). In the overparameterized setting, spectral methods and algorithms based on subspace embeddings can also find decompositions of rank k- r2 in polynomial time even for the more general low-rank approximation problem with an error that is constant factor competitive with the best rank-r de- composition [SWZ19 BCV14) The focus of our paper is to prove rigorous guarantees for the ALS algorithm, which is the most popular algorithm in practice.
2 Algorithm, Results, and Preliminaries
The Alternating Least Squares (ALS) algorithm for tensor decomposition has many variants. The version that we analyze is given in Algorithm 1F
Given a tensor T, the algorithm randomly initializes
'The version that we analyze is a parallel version of the commonly used ALS method, however seems like our techniques can be extended to give guarantees for the standard, sequential version of ALS. Our analysis for "sequential" ALS will appear in the arxiv version of the paper.

---

the three modes X,Y, E Rank of a decomposition, corresponding to model tensor
T
3q & 8
each iteration, the algorithm updates each mode individually in parallel to minimize the least squares objective:
min | T
Since i is multilinear in X, Y, Z. this least squares problem with respect to each mode. The least squares problem could have multiple optima, in fact due to the overparameterization, we expect this be the case. Typically, ALS is implemented using linear system solver for each of these subproblems [BK25]; this is also what we will analyze. The updates (Algorithm)
I
Lines 8
16
hence correspond to
x (++1) (Ta X, modes Y @ Z) @ Z())T!
((+1) flatten(T, mode Y, modes X @ 2) 3 ((0)T Tt
z(++)) flatten(T, mode Z, modes X @ () (())T.
Here use the shorthand flatten(T, mode A, modes B @ C*) mean that the order-3 tensor T reshaped into a matrix, by taking each n x n slice the B, C modes and vectorizing into an n² ni-dimensional row of the flattened matrix. There will be such Also, Mt refers to the Moore-Penrose pseudoinverse
corresponding mode A.
(This is explained in more detail in Section 2.1 of the matrix M.
Algorithm 1 Alternating Least Squares (ALS) for order-3 tensor decomposition
Require: Tensor T E paxxxn, rank of T' error tolerance
1: l < O(r²)
// rank of overparameterized model
2: (0) E ga N 1)nx*, y E Raxk x + ((0,1))** Z E Raxk + -NO0, 1)mk
3:
// raaadomlly initialize model
4: - 0
5:
while true do
6:
// V.YYY Y, Z updates can be evaluated parallel
7: // X update
8: errx, ((+1) e + minxeRex and arg minx of T T- Ek X, 8 @ 2
9:
if errx Se then
10: return X(++1), y()), z(t)
Y update
12: erry, ((+1)) + miny and arg miny exaxa of | Ei x!" & 8 2
13:
if erry then
14:
return X(9, ((+1), z
15:
Z update
16: errz, ((++)) min and arg min of -T- x 3 r Z
17: if err < then
return X (1), (0,,2 (++1)
19:
1-
We give the following guarantee for Algorithm In what follows, we will assume that ALS uses a sub-routine for solving the linear system in polynomial time; concretely, it computes the pseudo-inverse solution up to arbitrary precision & 0 in Frobenius norm in time polynomial in n, looglo//// (1/z). Theorem 2.1 (Guarantee for overparameterized ALSS). For any constant Co 0, there exists constants c(co) > 1 and no E (0, 1), such that the following holds. Let A, B, C E gaxr be the factor
5

---

matrices of the decomposition of a rank-r tensor T,
T= Σ
04 @ by 00 cz:
and suppose the condition numbers k(A), ()))))(()))))))))))))))))) S S r Then, given T, an error parameter and & E N satisfying cr I k I n with probability at least 1 o(1), Algorithm | runs in polynomial time and in (1) steps finds rank-k decomposition X,Y, E Boxk of That is, X, Y, Z satisfy
&
IT- Σ
The above theorem shows that ALS succeeds from random initialization with overparameterized rank = (fr²). For the theorem, we analyze standard Gaussian initializiation, the scale the random initialization does not matter much. For the above theorem, we assume that the factor matrices A, B and C' have condition numbers upper bounded by some large polynomial in This assumption on the condition numbers quite mild: for example, model It is weaker than incoherence or orthogonality assumptions, as the vectors in our setting can be quite correlated. Moreover, believe the assumption to an artifact of our analysis, and may not be necessary.
satisfied w.h.p. for a natural smoothed analysis
Finally, analysis also implies approximation guarantees for overparameterized ALS with & O(r2) under random initialization, in the more general low-rank approximation problem, where D Ei=1 04 & by + F., where || r is the error.
Theorem 2.2 (Low-rank tensor approximation using overparameterized ALS). For any constant co > O, there exists constants c c(co) 2 and no E (0, 1), such that the following holds. Let A, B, C nRxr be the decomposition rank-r tensor T,
T a a
and suppose the condition numbers (B)), (C) < p Then. given T. and an error parameter E, for cr < < no with probability at least o(1), Algorithm rans in polynomial time and in ((1) steps finds rank-k decomposition X, Y, 7 E Bonk of That is, X, Y,Y,2 Z satisfy
T
Σ
Iq 1
S po +
The above theorem gives ALS guarantee under overparameterization for the optimization problem in (2) in the general setting when OPT, > 0, and generalizes Theorem 2. (special case when OPT, = 0). The multiplicative factor loss in the objective compared to OPT, is polynomial in and independent of the ambient dimension n. To the best of our knowledge, such an approximation guarantec not known previously for ALS or other iterative algorithms like gradient descent.
2.1 Notation and Preliminaries
now introduce some notation and preliminaries that will used the rest of the paper. We refer to tensor T by its decomposition into factor matrices. That is, associate T with the matrices X, Y, Raxr, where r the rank of T and
T Σ 2 2
where 24, Mi, refer to columns i of X, Y, 2 respectively, and @ when applied vectors is the outer product. That is, each component x; @ y/s X 2; is an n X n x n tensor. Since each component an
'E.g. in the smoothed analysis model, you have an arbitrary matrix which is normalized to have columns of most unit length, with random perturbation of length 1 (r)

---

outer product of 3 vectors, this is an prder-3 tensor. Each direction of the outer product is referred to as mode, and we will sometimes refer to the modes of the tensor by the corresponding factor matrix, i.e., the X mode, Y mode, and % mode. (These are the analogues of the rows and columns of a matrix/order-2 tensor.) The squared Frobenius norm of tensor 7 is the sum of the squares of its entries.
will also be useful to interact with flattened forms of the tensors we analyze. We use O to refer to the Khatri-Rao product of two matrices Y, Z E IR*x,, which has columns given by
(Y C Z); = vecly; @ zi);
where vec(-) reformats an n matrix an 2 -ddmenniion vector. This is useful to flatten tensors into matrices. In particular, we have
yi 8 2112
Σ Te & veclys @ +1)1 || o T
This reshaping into matrix is exactly what arises in the least squares problem in Algorithm | (Lines 12 16). In Section 2 we describe the flattening operation for tensor with factor matrices Z. The flattening is just a reformatting of the entries of T, so computing it does not require explicit access to the factor matrices X, Y, Z. However, it indeed the case that
flatten(T, mode X, modes Y @ Z) = X(Y о T
which will be useful for our analysis.
Another useful tensor product on matrices is the Kronecker product which we refer to as & The Kronecker product of two matrices X E Ruxr Y E Rmxk is an nm x rk matrix that satisfies
(X S Veve((a @ b) vee( (X 8 Yb),
Va E R" bE IR..
(The entries can also be written explicitly as (X & Y) -Dtis = X V... Since the columns of Khatri-Rao product are flattenings of rank-1 matrices, this gives the following identity. For A E Raxr, B E IR mg and E R ,, E R4xg, we have
(A@ (X Y) (AX @ BY).
We will use the Moore-Penrose pseudoinverse M mm of matrix M E paxm This is defined matrix such that
Vo Null(M), Mx= M
Vy E Im(M), My y==0 0.
where the nullspace of M, (MM), is the subspace of vectors mapped to 0 by M: (fx) Mx оу). and the image of M, (MM) is the subspace of vectors that can be realized by the linear transformation
M: (Ly 3x, Ma = }}) Here and elsewhere we use (-) to denote the linear span. There are also a
few direct expressions for the pseudoinverse that will be useful to us. For M E Baxr, where r S M rank r (M is full column rank), we have
M MMMM--MM
For M E B"x", where S n, if M is rank r (M is full row rank), we have
Mt = M (MMT)-1
Analysis of the Algorithm
Fix tensor T = Σr a, b & e, for some rank-r decomposition A, C.C.C Raxr, Consider iteration of ALS on T. Without loss of generality, we focus on the update to mode Z (Algorithm I Line 3.
ALS will converge on this step ( y(t), ( fits T, i.e., the error between the model tensor and the true tensor is below For the purposes of the overview, we will ignore the error term, and refer to this as perfectly fitting the tensor.
'This overloads the notation that we use for the outer product on vectors. When applied to vectors we will always mean the outer product. When applied to matrices with dimensions larger than we will always mean the Kronecker product.
7

---

The least-squares problem for Z at time + 1 is to reconstruct the slices of T as linear combinations of the x!( y! That is, slice j of T is given by
Tos = E Casla, @b))
The least-squares problem along mode Z is then
2
min 2
T
&
8 2
Σ min T
Σ i=1
Zis
(
(0) 2 yi
1=1
F
which n independent least-squares problems, one for each slice of or row of Z. Thus, ALS will fit T and converge if, for every slice j. Tig. is realizable a linear combination of the (ar @ yt E [ Since every slice j of T is a linear combination {a; @ b, : : [r]].
sufficient condition for convergence is that
(fa; b, i (r])) S (fz)0 @ v8 ie [K1})
i.c., colspan(A B) C colspan (X o )
(4)
The two lines are reshapings of the same statement. Now suppose for moment that the columns
of (t) and (() were each drawn independently and randomly from colspan( A) and colspan B) respectively (for example, from standard Gaussians over the r-dimensional spaces). Then we would have that since k E ((r"),, with high probability
colspan( @ B) S colspan (X O y()),
(5)
where A @ B denotes the Kronecker product A with itself. Since colspan (A @ B) S colspan AA@ B), because the Khatri-Rao product is subset of the columns of the Kronecker product, (5) is sufficient to ensure convergence.
Of course, the columns of X and Y are not initialized randomly in the span of A and B, instead they are random in the whole n-dimensional space. This means that at initialization, each column of X (Y) can be thought of the sum of random vector in the span of A (B), and component orthogonal to A (B). Components orthogonal to the span of A (B) only make the Frobenius error of the decomposition higher, since they contribute terms that are orthogonal
T. That is, denote X = X + X-, where the columns of X are in the column span of A, and the columns of X- are orthogonal to column span of A. Then
k
+
Ui
8
1=1
F
F
The first step of ALS (Algorithm I Line 8) will set X that the second term is 0 which since Y and Z are randomly initialized means setting X- = O. the first step of ALS only set X Y-, 2- and did not modify X, Y, Z, then on the second step (4) would hold, and ALS would converge.
This is however not the
ALS updates X as the minimizer of the least squares objective. Thus (1) = -1) no longer has independent random columns. Instead it is function of ( and B. C. Our main technical insight is that, despite X y()) z(1) having this complex dependence each other and A, B and C, (4) holds with high probability. It is straightforward to show that after the first iteration, each of the factor matrices will be in the span of A, B and C' respectively, which means that (1) @ (!)) will be the span of A @ B. Thus, proving that (1) @ (1) has rank ? implics that colspan (1) c ( = colspan (A & B), then condition follows since colspan(A @ B) S colspan( @ B). This is captured by Theorem 4.1 which is the main technical component of our proof, and the focus of the next section.
4 Least Singular Value Bound through Anti- ontenConcentaation
For the proofs, we will refer to ((), y(),2() X, Y, 2. In this section we give overview of the proof of our claim that X @ y spans A & A when X, Y and Z are initialized randomly with their
8

---

entries being i..d. standard Gaussians and, in particular, show that this statement is true in robust sense. Formal statements of this claim as well as detailed proofs can be found in Appendix C We give an inverse polynomial in lower bound the least singular value of the matrix. Our main technical contribution proving the following theorem.
Theorem 4.1. Under the assumptions of Theorem 2.1 with probability at least 1 - o(1) we have that:
,,2 (X r
n (k)y
Assuming that A and B are mildly conditioned we can in fact turn our attention to showing least singular value bounds for the following matrix:
(r ( o (x E ERA
One main challenge is that the entries of the matrices (Y @ Z)t and (X @ 2) are random but highly dependent. While there have been powerful techniques developed recently for proving least singular value bounds of matrices with polynomial entries [BESV24), the random matrix in our setting does exhibit such structure and therefore difficult to reason about directly.
We proceed by first arguing about the matrix pseudoinverse by showing in Lemma C.I that with probability least 1 o(1),
1
YOZ)**
(Y Z)(1 Ei), n2
(V log(k)
where |E S O
k log(()
(and similarly for (X o Z)+
The high level intuition is that if the columns of the matrix that we are taking the pseudoinverse of were Gaussian vectors then they would be mostly orthogonal, meaning that the pseudoinverse would be close to the transpose of the matrix. Our analysis shows that the same intuition translates to matrices whose columns are tensor products Gaussian vectors.
Using that, it suffices, up to (nly(n) factors, to analyze the least singular value of the matrix:
L= ((B 2 C) (Y Z) E,)) ((AoC) (X Z) E2))
Furthermore, let:
i i- (B 2 2)) ((AOC) o 2))
Assume for now that we have a guarantee stating that (L) 2 poly(A) As we will discuss later, this is challenging, and much of our technical work is devoted to proving this. We can now use this to prove the existence a matrix M such that:
iMM = (BB C) (Y 2)) @ ((AOC)((X
Matrix M expresses the columns of the Kronecker product of matrices O) & Z) and (A CTT Z) as linear combinations the columns of their Khatri-Rao product. Such a matrix guaranteed to exist only because we have assumed that i. spans TRr"" Using (3) we can express as:
L = ((BOC) + (AAO)) (X 2)(1 E2))
( T 2)) ((A6C) (X @ Z)) (+
where E = I Eg E @ 1 E @ Eg; further by Lemma C.8 |E| S (v log(k) + log(k)) k)
We can now leverage the existence of matrix M to get that:
-= Z= + ME) where we have crucially used that, by definition of M, M 3 1) = 1. In Lemma C.3 we use that ( 2 1/poly(k) to prove that the spectral norm of M is also bounded by polynomial in k. Hence
pkly(k) = o(1)
MEJ| < |M |E|| <

---

when n is sufficiently large compared to k. We now have that:
(1 (1+ o(1))
o,2 (L)= (L(++ ME)) 2 (L,(LL amin (1 ME)
poly(k)
thus establishing the main least singular value claim.
In the above proof overview, we assumed lower bound on the least singular value of L. The proof of this claim quite technical and involves a careful net argument along with unti-concentration of low-degree polynomials of independent random variables [CWOI]] We first express the columns of the matrix in convenient way that factors the dependency of having on both sides of the Chatri-Rao product. We then argue by applying an c-net argument and showing that for every fixed vector in Rt,, the probability that the inner products between the fixed vector and all the columns of f. is negligible is exponentially small in k. The formal statement with detailed proof of it can be found in Lemma
5 Conclusion
Our work proves rigorous polynomial-time global convergence guarantees of the popular ALS method for tensor decomposition with moderate overparameterization of O(r²). has been challenging to establish rigorous guarantees for iterative heuristics that are the state-of-the-art in practice. Our analysis based on new matrix anticoncentration techniques to argue about the iterates, that differs significantly from previous approaches. Our theoretical results on overparameterization are also supported by empirical evaluations Appendix D It would be compelling to use these techniques to analyze gradient descent, or prove global convergence guarantees for other non-convex optimization heuristics.
Acknowledgments
The authors were supported by the NSF-funded Institute for Data, Econometrics, Algorithms and Learning (IDEAL) through the grant NSF ECCS-2216970 and the NSF via grant CCF-2154 1000 In addition, Vaidehi Srinivas was also partly supported by the Northwestern Presidential fellowship.
References
[AGH+14] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgar- sky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15, 2014.
[AGJ14] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates. arXiv preprint arXiv: 1xXXx::400.5180 2014.
[AGJ17] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Analyzing tensor power method dynamics in overcomplete regime. Journal of Machine Learning Research, 18, 2017.
[BCV14] Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan. Uniqueness of tensor decompositions with applications polynomial identifiability. Conference Learning Theory, 2014.
BESV24] Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, and Aravindan Vijayaraghavan. New tools for smoothed analysis: Least singular value bounds for random matrices with dependent entries. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 375-386, New York, NY, USA, 2024. Association for Computing Machinery.
[Bha97] Rajendra Bhatia. Matrix Analysis, volume 169, Springer, 1997.
10

---

[BK25] Grey Ballard and Tamara G. Kolda. Tensor Decompositions for Data Science. Cam- bridge University Press, 2025.
[BKS15] Boaz. Barak, Jonathan A. Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In Proceedings of the Symposium on Theory of Computing, 2015.
[CC70] Douglas Carroll and Jih-Jie Chang- Analysis of individual differences multi- dimensional scaling via n-way generalization of "eckart-young" decomposition. Psychometrika, 35(3):283-319, 1970.
[COB19] Lénaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buu E. Fox, and R. Garettt, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[CW01] Anthony Carbery and James Wright. Distributional and L norm inequalities for polynomials over convex bodies in R Math. Res. Lett., 8(3):233 23,248,,8, 2001.
[DLCC07] Lieven De Lathauwer, Josphine Castaing, and Jean-François Cardoso. Fourth-order cumulant-based blind identification of underdetermined mixtures. IEEE Trans. on Signal Processing, 55, 2007.
[Har70] Richard A. Harshman. Foundations of the parafac procedure: Models and conditions for an "explanatory" multimodal factor analysis. UCLA Working Papers in Phonetics, 16:1-84 84, 1970.
[Har72] Richard A. Harshman. Determination and proof of minimum uniqueness conditions for PARAFACI. UCLA Working Papers in Phonetics, 22:111-117 1972.
[Hás90] Johan Hästad, Tensor rank is np-complete. Journal of algorithms, 11(4):644 654, 1990.
[HJ12] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[HL13] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
[SSS166] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of uum-of-squares proofs: Tensor decomposition and planted sparse vectors. In STOC, 2016.
[]KA119] Majid Janzamin, Rong Ge, Jean Kossaifi, and Animashree Anandkumar. Spectral learning matrices and tensors. Foundations and Trends in Machine Learning, 12, 11 2019.
[JLV23] Nathaniel Johnston, Benjamin Lovitz, and Aravindan Vijayaraghavan. Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond In 2023 IEEE 64th Annual Symposium Foundations of Computer Science (FOCS), pages 1316-1336, Los Alamitos, CA, USA, November 2023. IEEE Computer Society,
[JO14] Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data, Advances in Neural Information Processing Systems, 27, 2014.
[KB09] Tamara G Kolda and Brett Bader. Tensor decompositions and applications. SIAM review, 51()), 2009.
KMW24] Pravesh K. Kothari, Ankur Moitra, and Alexander S. Wein. Overcomplete tensor decomposition via koszul flattenings, 2024.
[oo24]] Pascal Koiran. the uniqueness and computation of commuting extensions. Linear Algebra and its Applications, 703:645-666, 2024.

---

[KPAP19] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. Tensorly: Tensor learning python. Journal of Machine Learning Research(JMLR), 20(26), 2019.
[Lov10] Shachar Lovett. An elementary proof of anti-concentration of polynomials in gaussian variables. In Electronic Colloquium on Computational Complexity (ECCC), volume 17,
page 182, 2010.
[LRA93] S. E. Leurgans, R. T. Ross, and R. B. Abel. A decomposition for three-way way arrays. SIAM Journal on Matrix Analysis and Applications, 14(4):1064-1083, 1993.
[Ma21] Tengyu Ma. Why Do Local Methods Solve Nonconvex Problems?, page 465-485. Cambridge University Press, 2021.
[MMN18] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33): E7671, 2018.
[Moi18] Ankur Moitra. Algorithmic Aspects of Machine Learning. Cambridge University Press, 2018.
[MSS16] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In Proceedings of the 57th Annual IEEE Symposium on the Foundations Computer Science (FOCS), 2016.
[SV17] Vatsal Sharan and Gregory Valiant. Orthogonalized ALS: A theoretically principled tensor decomposition algorithm for practical use. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pages 3095-3104. PMLR, 06-11 Aug 2017.
[SWZ19] Zhao Song, David Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In Symposium Discrete Algorithms (SODA), 2019.
[Usc12] André Uschmajew. Local convergence of the alternating least squares algorithm for canonical tensor approximation. SIAM Journal on Matrix Analysis and Applications, 33(2):639-652, 2012.
[Ver18] Roman Vershynin. digenddimessonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[Vij20] Aravindan Vijayaraghavan. Beyond the Worst-Case Analysis of Algorithms, chapter 19 Efficient Tensor Decomposition. Cambridge University Press, 2020.
[WC14] Liqi Wang and Moody Chu. On the global convergence of the alternating least squares method for rank-one approximation to generic tensors. SIAM Journal Matrix Analysis and Applications, 35(3):0058-1022 2014.
[WWL+20] Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-parameteriized tensor decomposition. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21934-21 21944. Curran Associates, Inc., 2020.
12

---

A More Preliminaries
Our analysis involves various operations involving Khatri-Rao products, which are quite challenging to reason about. We also make extensive use of the Kronecker product defined in subsection 2.1 which are more natural products for matrices, and easier to reason about. We have the following simple facts about the Kronecker product:
Fact A.1. Let A, B E Baxk, then for the Kronecker product of A and B, it holds that:
1.
| @ BI
||||| |||||||B||
(6)
2.
| @ BllF = ||A|| |B
(7)
3.
min (A B) mmin (A)
amin (B)
(8)
The proof follows easily by noting that if U, E.V. V, and UnLis Vb are the singular value decompositions of A and B respectively then (U, 8 (2, @ (V, & V2) is singular value decomposition of matrix A @ B.
We now introduce some additional notation that we use in our analysis. For a matrix A we use II denote the projection matrix onto the subspace spanned by the columns of A. We use (x() to denote the i-th eigenvalue of matrix A, we also use a, (A) to denote the i-th singular value of matrix and x(A to denote the condition number of A. For the factor matrices A, and C of the ground truth we use k = max (M(AA,, x( xBB), k(C)).
For X, Y and Z being the random initializations of our algorithm use:
L L= ( ( (Ao0))
and also:
Lk - (B=0 R
(40))) (A
notice that L is the Khatri-Rao product of matrices (B o C) (Y @ Z) and (AoC) (x e while Lg is their Kronecker product. Furthermore, we use D₂ to denote the:
Dr. diag (,),,,))=_
The following expression is useful in our analysis:
Lemma A.2. For the columns of matrices (B C) (Y o Z) and (A T O have that:
(B (Y 6 (2);=D;;) BT yi and
(A (X Z); A Txx
Proof. We first observe that the j-th entry of vector (B の C*) (Y @ Z)z is given by (bj, m1) (cj, zi). The vector whose j-th entry is given by (bg yi) is B Left multiplying this by Dz, gives the result.
We now prove some useful claims.
Claim A.3. Given matrices A RRIxx B E R22xm we have
min { [|A|| om am (A) |[B|e] (
s I|A B < min ( {IAI|E||BI, ||||||
where ||||| 0 (A) is the spectral norm and (A) is the least singular value of the matrix A.
13

---

Proof. We have that
A BI = tt
(
Σ mm/mJ
aa 2 a 8.) |0:121411
(9)
For the upper bound, from
| ④ B
max
|b:
1
Σ
|a,112
|
max *E[m]
|b: - ||
mmmm
sc(m]
A similar proof shows that ||A
o
B
3 |B ||A|
For the lower bound, from 9 have
|| の BI
min
11:112
Σ
|a:113
||l xE[m]
min |b:122 S ||A|| (B)
xc (m
vE(m]
The following claim shows that for mildly conditioned decomposition, the Frobenius norm of the ground-truth tensor T can be sandwiched up to poly(r) factors by the corresponding norms of the factor matrices.
Claim A.4. Let T = EE 04 &
by
Cz.
Then
(A)
|| ||IICI,
where ||A||| = (A) is the spectral norm and (A) is the least singular value of the matrix A. A symmetric statement also holds with the Frobenius norm of or B instead of C being used.
Proof. First, we note that by considering appropriate flattening of the tensor,
a 8 0 IA(BoC)
(10)
We prove the lower bound first. Note that A has full column rank. Hence
||a[ o 1 ( F 2 (BIIC
by using lower bound in Claim A.3 Similarly for the upper bound, the upper bound in
Claim A.3 to conclude
||T|| (IA(B ( C/r ||||[,
as required.
We will use the classic perturbation bound for top-k singular space of matrix due to Davis and Kahan. The following is consequence that use in robust analysis [see Theorem VII.3.2 Bha97].
Fact A.5. Let M, M. Rdxm and let II denote the projection matrix the column space of M. and les TI denote the left singular space of M corresponding to the singular values larger than respectively. Then for universal constant 0
M M ca(M) 8'
(11)
where [| refers to the operator norm of M.
14

---

B Formal statements of the theorems
We give the formal versions of the main theorems below. Theorem B.1 (Guarantee for General decompositions). For any constant co there exists constant c = c(ca) 2 such that the following holds. Let A, B, C E TRixx be the decomposition of rank-r tensor T,
T
ag @ b, Cr.
and suppose the condition numbers Kf b(A)) x(C) r S no where To =ooco) constant. Then, given T, r, and an error parameter for k = op, Cop Cop(co) is a consinant, Algorithm I runs in polynomial time and in (1)) steps finds rank-k decomposition X, Y, Z E gnxk Tf i.e. X, Y, Z satisfy
k
2
10002
As discussed in the proof overview, Theorem B.1 uses the following theorem, generalized for asymmetric decompositions
Theorem B.2 (Generalization of Theorem 4.1 for asymmetric decompositions). Under the assump-
tions of Theorem B.I with probability least o(1), we have that:
xoo
0+2
n (k))
We give a proof of this Theorem in C.I
The following theorem is robust version of Theorem B. and gives a guarantee for low rank approximations
Theorem B.3 (Guarantee for low-rank approximations), For any constant co there exists constant e c(co) 2 such that the following holds. Let B,B,C C E Rax be matrices such that for
tensor tensor T:
T Σ a, 3c+
and suppose the condition number K(AA) RR B) k(C) p00 < no where "o 70(co) is constant. Then, given T, and an error parameter e, for k = Copt² with Cop = Cop being constant, Algorithm runs in polynomial time (in n, k; log(1/e) and in O(1) steps finds a rank-k
decomposition X, Y. Ba of i.e.. X,Y Y, Z satisfy
T
2 24
Err (ioooy(k,)) +
We note that Theorem B.1 is special case of Theorem B.3
We give proof B.3 in subsection C.2 this also implies the correctness of the more specialized Theorem B.I
C Analysis and Proofs
C.1 Least singular value bound for X o
In this subsection we give proof of Theorem B.2 In particular show that under the assumptions of Theorem B.I with probability 1 1 (1)):
0,2 (XOP)
> n (k))
We the following lemmas in analysis.
15

---

Lemma C.1
allows to go from the (X Z)t to matrix X ④ Z times 1/n² multiplied by identity plus an error matrix whose spectral norm we bound. It much easier to argue about matrix X @ Y when we express (X @ Z)1² and (Y @ Z)¹ like that.
Lemma C.1 (Pscudoinverse transpose simplification). Let X, Z E Runk be matrices with i.i.d. standard Gaussian random variables as entries, then there exists an absolute constant C such that, with probability at least
((X O 2)1)
ni (XOZ)(1+))
where | S 6V Cllo(())
+ 2 C log(k)
Proof. We have that, with probability 1, the columns of matrix (X @ Z) are linearly independent, meaning that we can express the pseudoinverse as:
(X + O) = (x=]
Taking transpose:
(x02)') = (x=2)")==xx0
=x=2
therefore suffices to show that:
n2 (x=2)
+
where E' has small spectral norm. Let for convenience:
n² (X (x
We show that all the eigenvalues of matrix W are close to 1 and use that to show that the inverse is close to identity in spectral norm. Specifically, let for convenience:
C' Colog())
+ k
a a(n k) 31/
log(k))
Y1
By Lemma C.4 we have that with probability at least 1 1 k. for every eigenvalue of W:
|) (W) 1| s a(n, k)
We condition that event. The eigenvalues of matrix W-1 are the reciprocals of the eigenvalues W, meaning that assuming that axn, k) S 1. we get that:
1
|A+WW (W-1)-
A (W)
D (W) 1|
A (W)
(nn, k)
ann,k)
< 22(n, k)
Now let E = W-1 - I and note that:
(N(E)) {>s (W-1) - 13
Furthermore, F is a symmetric matrix meaning that:
(o,(E)) {E)(())
{1) (W-1) - 1 -
which in turn implies that:
|B = (E)
< 2a(n, k)
the lemma follows.
16

---

is the main technical lemma for the proof, it gives us a least singular value bound for matrix I. and a bound on the Frobenius norm of matrix [.x. This allows us to bound matrix M by poly(k). Putting everything together we show that L L(I + M E) where L has non-negligible least singular value and | Ei] = o(1) giving us a non-negligible bound on the least singular value of I. which in turn gives us the bound on 0,2 [X o Y)
Lemma C.2
Lemma C.2 (Bound least singular value of L and Frob. norm of Lk). With probability at least
1 2 exp(-4r) (+)",, the following hold:
1. For the least singular value of matrix L, we have that:
o,(A)),(B),,(())
o, (L)
(12)
2w
where Cew is absolute constant coming from the Carbery- Wright inequality, Theorem
2. For the matrix:
Îx = (BoC) (AAOC)) (X (X
we have that its Frobenius norm is bounded by:
|| s 32 3 (A))
(13)
Proof. We first focus on item 1. We condition on the event Lemma C.5 which happens with
probability least 1 2/ and we have that for every i,j:
(r(C) 124
S (1) S v (log(k)o
We will prove the claim using the variational characterization of singular values, in particular we will show that for very IR"", we have that:
|| (B)
20
We consider fine enough E-net, N. of S where s(k) is inverse polynomial to be
determined later. Note that by Corollary 4.2.13 in [Ver8)) we have that [ S (?) Let u N. we will bound the probability that:
T s or (B),
k4,2
where 8 is a parameter be specified later. We have that:
[ T ull z (A))
s Vi: (Lo, un) s (B))
h4,2
klp2
S (B
(LL,s u))
(14)
ktp2
where we have used that all the columns of matrix are independent. W now fix an i and bound probability that (Le, u) < (B) We use that, by Lemma A.2 we can express the i-th column of matrix L. as:
= (D, (D,
17

---

where D., = -diag (ag, H) we can write the inner product with a as:
(In, u) = =(D2,, 91) 0 (D2, xi), (i), u)
= (((D., B (D=,A (yi & 1.), u)
= (y) @ 24. (BD,,) @ (ADs,)o )u)
For the least singular value of matrix BD., @ AD we have that:
0,2 ((BDz,) 0 (AD:.) or (BD (r (AD2;)
(B)
or(A)or Ke =)))²
(B(A),,(B)o,(C
11,2
let for convenience (AD,,, (AD,,) Ju, for the norm of we have that:
|| 2I(ADz) @ Jul
(A)o, (B)o,
k4p²
We interested in bounding the probability that Ky ny, u)| (0-(A)o-(B)o-107 We will use the Harbery-Wrightt inequality (ICW0I), (Lov10) to bound the probability. We have that f(z, v) = ||l|| (y @ x, u) is degree 2 polynomial, satisfying:
Var
(f (x))
Re: N 1)
Applying Theorem C.7 we get that there exists a constant Cow:
P (If( S 8) S Cew 52/2
which in turn gives us that:
P (Nw @ n, oR) s (B)())),1))00)(1)
Ccw 82/2
hdpp
We can now use equation 14 to get that:
( [LTul] s x (B) < (Cow 61/2)
kdp2
We now take a union bound over all elements of the E-net N, to get that with probability at least
1 (Cow 81/2)* & (2)², the bound holds. By Lemma C.6 we have that with probability at least
1 - exp(-Ar), for every i:
(x o 2)),1 (o) and (x 2)) 3ē- (A)o
We use that to bound the spectral norm of L. We first bound the norm of every column, we have that:
| (B @ Z)),II II(AA (x
32 - roog(k)) (B)
now use that the spectral norm is bounded by the Frobenius norm which is in turn bounded by vr times the largest norm of column to get that:
|| L & | S v max |لما| 3ö - (B)
18

---

Again applying the union-bound, we get that with probability at least 1 exp(-4r) (Cew 51/2)* & (?) (a) both of these events happen. We now take an arbitrary vector v E S we have that there exists a vector u E N such that 1|u- v/l S E:
| ml|
|| a + T. (u u)ll
2 || m|l | w))l
2 or (A)o,, (B))(,())) ||
k:4p2
(B) 32 (A))
kdpp
We take 8 = c and E so that we can take |Evi|| to be at least half as large as what we get on the g-net. In particular, we take:
85 6C è. k200+6.75
60 č. p400
6C č. x- 1og(k)5577/2
(B)
(4
we get that:
(B))
1 1/l 2
Cow
k5p2
6. (1
ē.
log(k))57772
(())
(B)),
Cowkhy2
20
(BO),
2C 2w
The failure probability is upper bounded by:
exp(-4r) (C2w 3
We analyze the third term. For convenience, let C" 18Ccwe, we have that:
x²
(Ccwwt/23k
3
(C"
=
k1/2
C²R20006.75
kCop2
We now take Cop 2(C" 2c, + 6.75 + 1) get that:
(12w8
The first item of the claim follows.
For the second item, recall that we have conditioned on the event that for every i:
(B o Z)), s V log(k)a (C) (A)) and (x Z)), < / r4)
19

---

We have that:
[|BBO) z)|l I V max [| c) (Y @ 2)
s 3r loo(k)o (A)ai(C)r
and similarly:
[AAC)] @ 1) S Vi max I(x 2)
< /32 log(k)o (A)oi(C) (C)r
We now easily bound the Kronecker product of the two matrices:
((BB)))) & (())))))))(()(())))))))))))))))) ( x))
-I( [| [| ((A Z)
32
Assuming that the events of Lemma C.2 hold, this lemma bounds the Frobenius norm of matrix M: Lemma C.3 (Existence and properties of M). Assuming that 12 and 13 of Lemma C.2 hold, then there exists a matrix M such that
1.
LM LK
(15)
2.
M(101)=1
(16)
3.
| 6CC " log(k))** + vk
(17)
Proof. We first observe that L, by Equation 12 spans H² which in particular implies that it spans the columns of matrix is which lie this space. This gives us the existence of a matrix M satisfying
15
We now observe that the i-th column of matrix Í, is equal to the ((i 1) + i)-th column of matrix Lx. In other words we have that:
L- (Lk) (i-1)8+s
where e is the i-th standard basis vector. This implies that take:
M(-11144 =
which in turn gives us that:
M(I о I) =I
and a6 holds. The rest of the columns of M we select them be the minimum norm vectors
such that M satisfies equation 15, In other words, for # (i - 1)k + i for every i, we let
M, Lt (Lx)
We now analyze the Frobenius norm of matrix M, defined as above. For j for which there exists an such that (i 1)k i, we have that:
M =
For j such that no such exists, we have that:
1 (Lx)
M ||
[+
[
[Lx)
|| (Ex)
1
0+2
20

---

We can now bound the Frobenius norm of matrix M:
| =
| 2
+ Σ
1
(Lxx) 1
f.
/1
Vk=
Σ
(Ex)
(1)
\
o,2
3
[ix
v
[1]
0,2
where have used that the square root is subadditive function. Using the bounds from 12 and 13 we get the result:
|| & V (CG
s Vk (lo
In Lemma C.4 we argue that the eigenvalues matrix (X @ Z) @ Z) are all close to 1 with high probability, we use this to show in Lemma C.I that we can replace the matrix (X o OY) by te (X ()(++))
Lemma C.4 (Eigenvalues close to 1). Let X, E Ruxk be random matrices with i.dd standard Gaussian random variables entries, then with probability at least t. we have that, for every i:
Ae ( (xx2 -1 -1
Clog(k)
s 3/
+ Coog(k)
n
where C' is an absolute constant
Proof. We will analyze the diagonal and non diagonal entries of the matrix (X @ ( and will show that the diagonal entries are concentrated very close to while the off off-diagonal entries are concentrated very close to O. We will then use Gersgorin disk theorem (Theorem 6.1.1 (H12)) get the result. For convenience, we let W we observe that:
TX @ Z)
+ 7) (X Z). For the off-diagonal entries
1 n²
Was
(r, M,,,,, 24)
For the inner product (I,, œ,)) we have:
(z), Σ (1)))())))
By Lemma 2.2.7 in [Ver88 each summand is a subexponential random variable with subexponential norm:
(I),( I ||x;(1) (1ll
k?
where K is the sub-Gaussian norm of the standard Gaussian. Using Bernstein's 's inequality, Theorem
2.8.1 in [Ver18), (the inner product a sum of nub-exponential random variables) we get that:
IP (1
(1, 225) 2
< exx
[-emin
nK? K
21

---

for some absolute constant Setting /Cnloggk)) for C₁ being large enough constant we have that with probability at least 1
13.
C1 S log(k)
(ar,, mz3)
(18)
n
Similarly, we have that, with probability at least
:=:
C1 K2 log(k*)
2z)
S
(19)
n
For the diagonal entries of the matrix M we have that:
W = ||=;||2 ||:1|
Σi= (1) and use the fact that there exists an absolute constant C such that x; (7)2 1 is subexponential random variable with subexponential norm:
We write =
(1=(()) - l1 s CK2
We apply Bernstein's 's inequality again, to get that:
t²
Σ - (0 -1
-122 2t) S exp --
P
ČK2n
K
We set / C2n (kg(k: for large enough constant C22 get that with probability at least we have that:
1
C2 log(k)
||x;1| -
(20)
n
n
Similarly, with probability at least 1 13. we have that:
|
1
1
Ca log(k)
(21)
n
We get that, by the union bound, with probability at least equations 18 19 and 21 hold for every j. Setting C = max(C1, C2), with probability at least k for the off diagonal entries of
matrix (Z O X) (Z o X) we get that:
W S C'log(k)
n
And for all diagonal entries, assuming that
C Clog(k)
< get that:
72
| logg(k)
W - 1| S 31
We now apply Gershgorin disc theorem (Theorem 6.1.1 in HJI2)) and the the fact that + (Z
X) T (Z X) is symmetric and therefore all its eigenvalues real to get that, for every
A (W) E
U j=1
$ S -- --
S Σ Wral
173
C s E R: 11-1 3//
C Cloog kk)
k
Clog(k)
where from the first the second line the triangle inequality.
In Lemma C.5 we give bounds upper and lower bounds for the inner products (cy, 2i), needed to bound the least singular value of matrix and the Frobenius norm of matrix ŻK.
22

---

Lemma C.5. With probability at least 1 over the randomness in Z, we have that for every and for every j:
(C(C) krr
S Ke, 2i)l (6log(H)o1(C)
Proof. For fixed i.j. the inner product between ej and 24 has distribution (cf,2)) NO.,, For the lower bound, we have that:
(Kc,, 2:0
or((')
(1
|lyl| (c,, 21)
1
S o,(C)
=
2
h²r b.rr-1ay/1
1
(C)
22T
k2rlly
cC
k
where we have used that [ey (ej m.) ~ N 1) and that the density of the standard Gaussian is upper bounded by V2x"
We now use the union bound to get that:
(C)
(C)
3i Ke, 21 1 12T
k rrrllegl
where we have used that for every j. |cyll 2 (C, For the upper bound we again fix i, and use that |e (g), xz) [00, 1). Using Proposition 2.1.2 in [Ver18), we have that:
2
12
P
|e,
(c,
2i)
2
t
v
2n
exp
2
Letting log((()))) 2 1, we get that:
1 ||, (c,, (c)
2
1
IP
2 2log(A+3)
V
1:3
By the union bound and the fact that for every j. ||e/l| S (C)(
IP
Bijj Keg, 21)1 2 22log(h3) (0))
-
i=1 f=1
kr
13
Using again the union bound we have that with probability at least for every i,
(C( k2r I [c, 2i)l (llog(k)-or((
Lemma C.6 (Bound on columns). Assume that for every i,j. we have that Kej zill /6 (C)) then with probability at least 1 - exp(-4r) we have that for every it
S
o 2)), s (og' (I((AC))((X 2)), s (4)
and
where ē is a large enough constant.
23

---

Proof. Fix an and recall that by Lemma A.2
((A@C) 2)) D=; AT
We focus the norm of A2 Tú. we have that:
D A 2, D.. (II
= D AI
where we have used that II A and that any projection matrix symmetric, We have that:
|2, A mill = [P (TAa;;)
< D2, ||]]]]]
DD: ||||| ||T
max Keg, 24)1 01 [
I log(())) Jo (A)]
where from line to line 3 we have used that the operator norm is submultiplicative. From line 3 to line 4 that the operator norm of diagonal matrix is equal to the largest entry in absolute value and from line 4 to line 5 our assumption on (eg, 2,)l. Similarly, get that:
2|,, yill S 2 logg(k>)) Jan (C))(())|[ииы)
We now use that || has the same distribution that of a norm of an dimensional random vector with i.dd, standard Gaussian entries, by Theorem 3.1.1 in [ee18], we get that:
IP aa Vrl 2 t) s 2cxp(-et²)
Applying this bound with 1 (V2/2 V) (we will specify é later) well the union bound, we get that:
čr 2
čr
P 3i: [A
or [B
< 4k exp(
2
We take č to be a large enough constant so that 4k exp( - (2/22- - 1))r) S exp(-4r) The definition of & in Lemma C.2 depends on é, because Cop 2(18CCW 2+ 20o 7.75), nevertheless select large enough so that, for every r:
2 (18Ccw8 + 20g + 8.75) 12 exp (- (-(V//2-1)'>) s Eexp(-4r)
We conclude that, with probability at least 1 - exp (-4r), for every i:
|| T xill S / ör log A:3 (o (A)o (C) and
[D B will v ör log( (B)o (C).
The claim follows.
Theorem C.7. Let f(x)= = f1,,, I2, In) be a degree d polynomial such that Varif] = when a standard n-dimensional Gaussian vector, then for every and for every 0, have that:
P (),10
(1f(z) - < $) S (d)) g//d
Claim C.8. Let A,B Buxk then:
II B| ||| ||B||
Proof. We first observe that the columns of A O B are a subset of the columns of the matrix A @ B, meaning that:
A O B < A &
B
that:
||A C B
|A|
|B
24

---

Proof of Theorem B.2 We analyze the least singular value of matrix X @ Y. Using Equation 3 we
can rewrite the matrix X ④ y as:
xo²=(A0 B) (1B00T0())) o (460TTx000))
We now have that:
8 2 8)
2 0, o,
Op 0,2 (A)o,,(BB)), ((BO))( : (1
B)
We can, without loss of generality, using our assumption on the condition numbers of A, B and C, assume that for the least singular values of A,B and C, we have that or (A) 2 poly(r) 0, (B) Z poly(r) and or (C) poly(r) (otherwise can rescale the tensor I that this holds):
0,2 8 (xOP)2 poly(k) 0,2 ((BBO))rO2))) @ (IxOA)(XO2))
It therefore suffices to analyze the least singular value of matrix:
(IBOC) 2) (xx
By Lemma C.1 we have that with probability least 2. k²
(Y 2)²² (Y @ Z) + E1) and
n²
(X @ 2) T
1
(X o 2) (I E2)
n
where [Ei],, < /6 (olog(k)
+ 2 log(k) (C is an absolute constant). We now have that:
(BOC)
1 -
where we have used L to denote:
I (B (Y 2T+ Fn)) (x Fi)) we therefore, have that:
(AATTTxX""(( = -
0,2 Hence, it suffices, in order to prove the claim, to bound the least singular value of matrix by poly(k] We first analyze the matrix:
i. = (BOC) o ( (x@x))
(X o 2)).
By Lemma C.2 we have that with probability at least 1 - cxp((-4r (2) n
o,a (i) 2 (B)
(22)
ho
and that for matrix:
Lx - (==(BBB)) ( (Y 2)) @ (A
Its Frobenius norm is bounded:
Lix
< (A)
(23)
'i would be equal to L if Ei Es =
25

---

By Lemma assuming that equations 22 and 23 hold, there exists matrix M such that 15
16
and 17 hold. By the union bound, with probability at least 1 - 1 exp (-4r) the events of Lemma and C.2
o
both hold. We now have that, using Equation 3
L (BOO) (Y o1 @ (IAOO) (X (X 2) (1(+)
-(BOO) ( (Y 0z) @ ((AOO) (x ((++E) (1)
Lx (+
where we have used E to denote the matrix T E2 + E1 @ + E1 Eg. By Claim C.8 and assuming that n is large enough compared to k, follows that:
| -
E2ll + E
I1 + E O E21
- E1
E2l
E1ll
|E2l
(l)g(A))
2k
$ 3 6
C log(k)
n2
We can now use matrix M:
L = (
- E)
=L(I+ME)
where we have used that M such that M(1 1)= least singular value of matrix L. We use the variational characterization of singular values:
= I. We will use this expression to analyze the
2,2 (L) = o,, (ME))))
(II (ME) )LT)
0,2
min
|| IT+ (MF) ii. u
uER"
[u]|==
2 min Jmin (T + MF). [lt.Tul
"ER*
||||=1
2 Omin (I + (MM))= 022 L
We have the bound on the least singular value of L, we only have analyze the least singular value of matrix I + M.. We argue by showing that M E' has small spectral norm. We have that:
|MME < |M] || ||E||
Assuming n 2 A for small enough constant To. we get that:
|M] || = o(1)
Using the variational characterization of the singular values, we have that: muin (I + ME)
min
|[(T M)) ull
MER"
[|a]|=1
min
|[uu|| - ||M
wER"
||]|=i
2 1 - -I
1 o(1)
This concludes the proof.
26

---

C.2 Robust Analysis
Recall that the tensor T has a decomposition of rank given by factor matrices A, B, C x
xx that approximates i., T = Ei=1 @b & Err with OPT = |[ - & = Errl| P.
The following lemma relates the objective value to singular values of different matrices related the updates.
Lemma C.9. [Objective value in the second iteration] Suppose x y(I) be the iterates of Algo- rithm I after the updates of the first iteration. Let & = X @ Y and & = - @ Y where X, Y are the updates after the first iteration when there is error. Then we have that the loss objective value in the second iteration is at most
0 -110-1111
$1 171P
1
20
20PT.
(24)
0x2
E=1
Proof. We prove this statement using the above lemmas, and using Davis-Kahan theorem for pertur- bations of top singular spaces.
To bound the objective value in the second iteration as (24 use the characterization of least squares value being the squared perpendicular distance of the target vector from the span of the columns i.e., IT is the projection matrix onto the subspace orthogonal the column span of
② == x Y then
1 = 1 flatten modes X & Y. mode Z) |
2
n ((AO + +
where FS E RBnxx xn is the flattening of the tensor Err. Let Hs be the projection matrix on to the span of the columns of X @ Y, and I be the projection matrix for the subspace orthogonal to it.
2
IT= (A B)CT + FFa)l
|T (Mo + [15) (A @ B)CT + Es) l
1|- + m (AA (AOB)CT)) + +I
(A B)CT)
1|2 + 21
- (A 3 B)C
where we have used that 1 (A の B)C = 0, since +- = NoP contains A @ B w.h.p. from the previous non-robust analysis. Furthermore, since the top 2² singular values M are separated from the least singular value of corresponding to I (i.e., 0, since this corresponds to the nullspace of
) we have by the Davis-Kale Kahan theorem (see Fact A.5
O 1))
|| <
(.)
T
(1) J
2 |2)
< 2 no||| ((A B)T || E1
c/ Φ
T 12 I
20PT.
for some constant e 0.
The following claims bound the different terms in
24 Lemma
C.I1
27

---

Lemma C.10. [Projections onto the column space Yf @ Z] Let Q E R² be arbitrary matrix and Y, Z E R be random matrices with i.i.d ( 1) entries. There exists universal constant
> 0 such that with probability at least 1 o(1
10T (Y o 23))) 11 -
< 1|Q|I
(cV (CVklog(kr)
(25)
Proof. From Lemma
C.I we have that
1 1 o (): where | = oz,n S 1
((Y o 2)t)
for our choice of parameters. Hence, will suffice upper bound ||Q
T (Y Z)Ila-
Each of the columns of Y @ Z is an i.idd random vector distributed identically to y @ 2 where y: N(,, Inxa). Consider fixed j [r], i [k]. For any / 1, from concentration of quadratic multivariate polynomials due to Hanson- Hanson-Wright inequality [see e.g.. Ver18), we have that the (j, i)th entry of Q" (Y @ Z) can be written as
P [10,, (Y 22 (10]1l=] = v, Y.2
[ > 11Q/11l]
12 2
(-
I 2exp
S 2exp
2|10, P t||
3(kr)²
for t = (log(kr)) The lemma follows after a union bound to get an upper bound on the magnitude of each of the kr entries of the matrix.
This in turns leads to the following claim.
Lemma C.11. [Perturbation of the spectrum with noise] Let (1), (I) be the iterates of Algorithm
1 after the updates of the first iteration. Let & = x o y()) and X, y denote the updates after the first iteration when there is error. Then with high probability o(1), we have for +b 8 ) Y that
④ 2 - -
S
VOPT
O ((kloo((kr))
(kr))
F+ +
V (26)
n2
A similar claim holds for (2) о ( and (11) O (1) as well.
In the above expression OPT
|||C||
Proof. Recall that = E 2 b, @ c + Err, where |Err|] = VOPT. Moreover, for the
flattening E1, Eg paxnn along the first and second modes of Err, we have with probability
1 - o(1) from Lemma C.10 that that
x (A(B@C) о) + +1i ((Y o 2 A(B +E ((Y 2)t)
=X+Ei((Y o Z)
= =X+Ex.
where ||E < |Ex||e VOPT. Vklog(kr) And similarly, y()) = -()=-=
n²
Ey, where |Ey S VOPT. V log(rr) n²
28

---

Furthermore,
| A(BOO)) - (0Y @ (2)))" l|f
cVklog(kr)
| o C| by Lemma C.10
n²
c/ log(r))
|||||| B|||C||
n²
by Claim
A.3 We have similar bound for | ||. Hence, we have
|
8o 11
|[ Ex) (P + Ey) 8 Y S Ex o &1++18 o Erll+ e Eyll
|| + X Ex Ey
(using Claim A.3
@klo VOPT
|||A||
|B|||
||0||= + VOPT)
n²
We now finish the proof of Theorem
B.3
Our analysis will work with any algorithm that computes the pseudoinverse solution. For any M, we find M such that
Proof of Theorem B.3
|| MI S. mi
Without loss of generality, we can assume that ||||| r 1 (for scaling), and || = B| 1 ||C|| (since we can redistribute the mass among the factors of any decomposition arbitrarily). Let us denote by OPT = || and к
(A)), x²( (), k(C)). By Claim A.4 we have that 1 1 || S r S p +200 For our purposes, we can think of OPT 2 E, since the guarantee and proof works up any upper bound problem up to precision e in time polynomial n, d, log(1/e). We can ignore this e this robust analysis, since it is dominated by the error terms in the tensor, and the intermediate steps. Also note that OPT < 1; in fact, it will be useful to think of OPT < 1/poly(k,r) r). since otherwise the trivial bound suffices.
Errlle. The algorithm in every iteration solves least squares
We can bound the objective value the second iteration using Lemma C.9 and combine with Lemma C.1l to get
< 2(PT E) + 0(1) 1 1
IT
(2)2
11
1+ O log (rk)) P
O(OPT)
(2),
O log (rk)) 1+
O(OPT)
(
O(OPT) poly r).
by using the bound of 0,2 (n*poly(k: (k, r) from Theorem B.2 and the bound on k in the assumptions on Theorem B.3 This concludes the proof.
29

---

D Experimental Evaluation
Our theoretical results guarantee convergence of Algorithm | when the overparameterization k: O(r²). In our experiments we investigate whether this overparameterizatioo factor is also observed in practice, and what the leading constant in the dependence is. The second question is how much overparameteriizatoo is needed i.e., does ALS require k = Q((2)) to succeed? Our experiments suggests that both these questions are true.
Algorithm is non-standard version of the ALS algorithm because in each iteration, it performs the updates to each mode in parallel. That is, x(++1) y(++), Z(++1) are all a function of X y()) Z((), This is in contrast to the standard version of ALS which updates the modes sequentially. That is, ( will depend on
as in the parallel version, but then y(++1) will depend on
X(+1), z and 7((11 will depend on ((++1, y(+1), Our theoretical results focus on the parallel update version (Algorithm [T) because it is easier to analyze. In our experiments, we evaluate both the parallel-update and the standard sequential versions of ALS, to see what the effect of overparametcrization is.
D.1 Experimental setup
To evaluate the parallel-update version of ALS (Algorithm [ we implemented non-optimized version using the scipy least squares solver. For each n, k that we analyze, we run 20 trials. For each trial generate 3 random make up our ground truth tensor. We initialize the factors of our model to be fully random n x matrices. For all 200 and 500 set the maximum number of iterations to be 20, due to computational constraints.
factor matrices (each entry is independent Gaussian) to
To evaluate standard ALS, we used the parafac method from the TensorLy library KPAP19, which provides an optimized version of the standard (sequential) ALS method. As for parallel-update ALS, for each n, r, k that we analyze we run 20 trials, and for each trial we generate 3 random (Gaussian) n X r factor matrices to make up our ground truth tensor. We then call parafac on this tensor with random initialization! For 500 we set the maximum number of iterations to be 100, and for n 1000 we set the maximum number of iterations to be 20, due to computational constraints.
We provide python code to run both experimental setups as part of the supplementary material.
D.2 Paratlel-updated ALS discussion
2 suffices. Our theoretical results guarantee that parallel-update ALS (Algorithm I should converge in O(1) steps as long as k = 2) Our experiments validate that this holds for k: = r² with no leading constant. In Figure [ we plot the errors of running Algorithm [ for n 200, E {8, 11, 14. 17, 20), and various values of & that depend on the setting of r. We see that consistently across all settings r. Algorithm connsstenty fails to converge for any value k: < 2
and consistently converges for k 2 y².
Our theoretical results guarantee that, once is sufficiently larger than k. the overparameterized rank necessary for parallel-udatt ALS (Algorithm[] [T to succeed has no dependence on n. In Figure 2 we plot the errors of running Algorithm| [ for r' 8, and n e {200,, 500). We observe that there is indeed no apparent difference in the results.
D.3 Standard ALS discussion
2 suffices for standard ALS. While our theoretical results apply to the parallel-update version of ALS, we observe that overparamettrrization & = r seems to suffice to ensure convergence for the standard sequential version of ALS as well. We run this experiment for n = 500 and various values of and k. and the results can be found in Figure[3] Figure 4 Figure 5 Figure 6 Figure 77] Figure X Figure In all of these experiments, we see that ALS starts to converge for values of that are less than r Our theoretical result for the parallel-update ALS guarantees that the overparameterization necessary to ensure convergence should have no dependence on n. To evaluate whether this is true for
We use fully random initialization opposed to the default SVD initialization, which deviates significantly from what we analyze in this work.
30

---

standard ALS, we provide Figure 9 and Figure 10 which both evaluate 20 and the same values of & for two different values of n (n 500 and 1000). We observe that the different choices of n do not appear to have any significant impact on the error of standard ALS as function of the overparameterivation.
Comparison to parallel-update ALS. We see that in comparison to the parallel-update version of ALS, the standard version has a more graceful degradation of error as a function of k. While do not have theoretical result that proves that standard ALS performs only better than the parallel-update version we analyze, does appear in our experiments that this the case. Even though standard ALS converges for smaller values of than the parallel-update ALS, note that many of our experiments, including Figure Figure X Figure 9 and Figure [T] seem to display that standard ALS experiences instability values of k very close to r², that it does not experience for other nearby values of k. We view this as an interesting phenomenon to investigate in future work.
Necessary overparameterization. Our theoretical results guarantee that parallel-update ALS converges for k = (2(r9). Our experimental results suggest that parallel-update ALS converges exactly when 2 p (with no leading constant). Our experiments also suggest that standard (sequential) ALS converges for values of k < r². However, we observe that even though the input tensors our experiment are chosen randomly from nicely-behaved distribution, standard ALS still requires l significantly larger than to converge. Our results are inconclusive as to what dependency must have on r to ensure convergence. We view it as an exciting future direction both theoretical and experimental work to understand the overparameterization necessary ensure convergence of standard ALS.
D.4 Data
Parallel-update ALS relative error 200)
35
Threshold 0.01
rm
30
17
7=
Average Rolalive Enor
2.0
1.5
0.5
00
-2
(70-1
(00
(!*) +1
(*0*r
0*0
Overparametenizaaionn
Figure 1: Results of rumning the parallel-update version of ALS (Algorithm 1 for n 200, various values of r, and various values of & that depend on We see that this method consistently fails to converge for & < r2 and consistently converges for k 2 ? For this experiment we run ALS for maximum of 20 iterations per trial. For trials where the method converged, it always converged in iterations, which is consistent with our theoretical result. The reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure
31

---

Paralisl-update
B)
Threshold 01 n 200
500
3.0
Average Relalive Etror
2.5
2.0
1.5
0.5
0.0
62.5 65.0 67.5
70.0
72,5
75.0
77.5
80.0
Overparameteriiztions
Figure 2: Results of running the parallel-update version of ALS (Algorithm for 8, two values of n, and various values of & that depend on r. We see that this method consistently fails to converge for & x² and consistently converges for k: 2 ,², For this experiment maximum of 20 iterations per trial. For trials where the method converged, it always converged in iterations, which consistent with theoretical result. The reported values aggregated over 20 independent trials, with eтror bars corresponding to one standard deviation. The data for this plot can be found in Figure
ALS for
Standard ALS for 8, 500
0.40
0.30
Mean Relative Error
0.25
0.15
0.10
0.05
0.00
10
20
50
60
70
(Over/paramettriiationn
Figure 3: Results of rumning standard ALS (parafac by TensorLy (KPAP19] for n 500, and various values of k. We observe that the стrо degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r 8, but smaller than ,2 = 64. For this experiment we run ALS for maximum of 100 iterations per trial. The reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure 13
32

---

Standard ALS for 10, n 500
0.35
0.30
0.25
Mean Relative Error
0.20
0.15
0.10
0.05
0.00
20
40
60
80 100
(Overlparameterization k
Figure 4: Results of running standard ALS (parafac by TensorLy [КPAР19] for n = 500, r 10 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r 10, but smaller than , 100. For this experiment reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure 14
run ALS for maximum of 100 iterations per trial. The
33

---

Standard ALS for 12, n 500
0.30
Mean Relative Error
0.20
0.15
0.10
0.05
0.00
20
40
60
80
100
120
140
160
(Over)parameterization k
Figure 5: Results of running standard ALS (parafac by TensorLy [КРАР19] for n = 500, r 12 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r = 12, but smaller run ALS for maximum of 100 iterations per trial. The
than , 144. For this experiment reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure 15
34

---

Standard ALS for 14, n 500
0.25
0.20
Mean Relative Error
0.10
0.05
50
100
150
200
(Overlparameterization k
Figure 6: Results of rumning standard ALS (parafac by TensorLy [КPAPI9] for n = 500, r 14 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r = 14, but smaller than , 196. For this experiment reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure T6
run ALS for maximum of 100 iterations per trial. The
35

---

Standard ALS for 16, n 500
0.25
0.20
Mean Relative Error
0.15
0.10
0.00
50
100
150
200
250
300
(Overlparameteriaation k
Figure 7: Results of running standard ALS (parafac by TensorLy [КРАР19] for n = 500, r 16 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r 16, but smaller than r² 256. We also observe that standard ALS seems experience some instability for values of very close to 72 = 256. For this experiment we run ALS for a maximum of 100 iterations per trial. The reported values aggregated over 20 independent trials, with error bars corresponding one standard deviation. The data for this plot can be found in Figure T3
36

---

Standard ALS for 18, n 500
0.25
0.20
Mean Relative Error
0.15
0.00
50
100
150
200
250
300 350
(Overlparameterization
Figure 8: Results of running standard ALS (parafac by TensorLy [РРАР19] for n = 500, r = 18 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r = 18, but smaller than r² 324. We also observe that standard ALS seems experience some instability for values of very close to 22 = 324. For this experiment we run ALS for a maximum of 100 iterations per trial. The reported values aggregated over 20 independent trials, with error bars corresponding one standard deviation. The data for this plot can be found in Figure T8
37

---

Standard ALS for 20, n 500
0.30
0.25
Mean Relative Error
0.20
0.15
0.10
0.05
0.00
100
200
300
400
(Overiparameterizatio k
Figure 9: Results of running standard ALS (parafac by TensorLy [КPAP19] for n = 500, r 20 and various values of k. We observe that the error degrades gracefully as function of k. The minimum necessary to ensure convergence seems to be significantly larger than r = 20, but smaller than r² 400. We also observe that standard ALS seems experience some instability for values of very close to 72 = 400. For this experiment we run ALS for a maximum of 100 iterations per trial. The reported values aggregated over 20 independent trials, with error bars corresponding one standard deviation. The data for this plot can be found in Figure
38

---

Standard ALS for 20, n 1000
0.30
Mean Relative Error
0.15
N
0.10
0.05
0.00
100
200
300
400
(Over/parameterizaton k
Figure 10:
Results of running standard ALS (parafac by TensorLy (КРАР19] for n 1000,
20 and various values of k. We observe the results of this experiment are very similar to Figure 9 suggesting that convergence standard ALS is function of k and not n. For this experiment we run ALS for maximum of 100 iterations per trial. The reported values are aggregated over 20 independent trials, with error bars corresponding to one standard deviation. The data for this plot can be found in Figure 19
39

---

mean
std. dev
22
1.35
1.07
r²
1.3
0.855
8
y
5,99e-13
9,46e-13 13
+1
3.21e-14
1.85e-14
p² +2
2.86e-14
1.89e-14
8
r² tr
4.92c-14
1.66e-14 14
8
p² 2r
3.09c-14
4.6e-15
11
r²
1.18
0.813
11 -2-1 1.21
0.511
11 p²
3.38e-13
8.14c-13
p
4.66e-14
4.06e-14
11 r² +2+2
2.81e-14
1.21e-14
11 p² tr
1.25e-14
2.1e-15
8² 2r
9.46e-15
1.23e-15
14 42 2
1.03
0.659
14 p² 1 1.73
1.69
72
9,44e-13
3.14c-12
14 +1
6,93e-14
1.03e-13
14 +2+2
3,96e-14
1.49e-14
1²
1.54c-14
1.53e-15
14 +r
3,67e-14
4.32e-15
17 r² - 2
1.22
0.628
17 p²
1.18
0.731
17 x2
23
5.84e-13
17
x2 11
5.83e-14
3.82e-14
17
r² +2
4.44--1
1.36e-14
17
7² +T
1.56c-14
1.29c-15
17
72 2 2r
2r
95
6.06e-16
20
r²
1.02
0.376
20
1
1.43
1.07
20
72
9.33e-13
1.04e-12
20
21
8.34e-14
3.87e-14
20
+2
7.58e-14
2.77e-14
20
2T
1,49e-14
8.28e-16
20
22
+
2r
3.83e-14
3.45e-15
Figure 11: Data used to generate Figure ! For these experiments n 200, and the maximum number
of iterations of ALS is 20. The reported values are aggregated over 20 independent trials.
40

---

72
k
mean
std. dev
200
22
2
1.35
1.07
200
22
1.3
0.855
200
8
r
5.99e-13
9,46e-13
200
2 +1
3.21e-14
1.85e-14
200
2 +
2.86e-14
1.89e-14
200
8
,2 +r
4.92e-14
1.66e-14
200
p2 + 2r
3,09c-14
4.6c-15
500
2 2
1.5
1.31
500
8
r2 -
1.81
1.88
500
7
2.67e-12
1.11e111
500
+1
3.36e-14
1.91e-14
500
+2
2.72e-14
1.25e-14
500
,2 +
1.11e-14
2.17e-15
500
2 2r
6.7e-15
1.29e-15
Figure 12: Data used to generate Figure
2 For these experiments the maximum number of iterations
of ALS is 20. The reported values are aggregated over 20 independent trials.
r
mean
std. dev.
8 0.279915
0.111048
8
16
0.106255
0.071116
8
32
0.0293
0.032489
8
48
0.00011
0.000177
8
56
0.0
0.0
8
60
0.0
0.0
8
63
0.0
0.0
8
64
0.0
0.0
8
65
0.0
0.0
8
72
0.0
0.0
8 80
5e-06
2.2e-05
Figure 13: Data used to generate Figure For this experiment n = 500, and the maximum number of iterations of ALS was 100. The reported values aggregated over 20 independent trials.
mean
std. dev.
10
10
0.237
0.100775
10
20
0.105275
0.073401
10
40
0.03214
0,025882
10
50
0.01725
0.014379
10
60
0.009715
0.01181
10
80
5e-05
6.
10
90
0.0
0.0
10
95
0,0
0.0
10
99
3.5e-05
0.000157
10
100
4.6e-05
0.000113
Figure 14: Data used generate Figure For this experiment n 500, and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
41

---

mean
std. dev.
12
12
0.241995
0.075478
12
24
0.10385
0,057524
12
48
0.052115
0.037644
12
72
0.020825
0.015514
12
96
0.006375
0.006497
12
120
1.5e-05
3.7e-05
12
132
0.0
0.0
12
138
0.0
0.0
12
143
0.0
0.0
12
144
0.0
0.0
12
145
0.0
0.0
12
156
2c-05
8,9e-05
12
168
0.0
0.0
Figure 15: Data used generate Figure
For this experiment n 500, and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
mean
std. dev.
14
0.1976
0.08427
14
28
0.081565
0.065547
56
0.054265
0.03741
14
86
0,037515
0,023547
98
0.02151
0.015892
14
112
0.01377
0.011933
140
0.001525
0.002253
14
168
1e-05
3.1e-05
182
0.0
0.0
14
189
0.0
0.0
14
195
0.0
0.0
14
196
5e-06
2.2e-05
14
197
1e-05
3.1e-05
14
210
0.0
0.0
14
224
0.00027
0.001207
Figure 16: Data used generate Figure
For this experiment n 500. and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
42

---

mean
std. dev.
16
16
0.20394
0.078098
16
32
0,07173
0,045191
16
64
0.065095
0.039075
16
96
0.04665
0.02052
16
128
0.023405
0.015258
16
160
0.008025
0,007481
16
192
0.000725
0.001254
16
224
5e-06
2.2e-05
16
240
0.0
0.0
16
248
0.0
0.0
16
255
0,00012
0.000537
16
256
3.5e-05
7.5e-05
16
257
0,00272
0.011766
16
272
5e-06
2.2e-05
16
288
0.000575
0.001772
Figure 17: Data used to generate Figure For this experiment n = 500, and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
mean
std. dev.
18
18
0.201895
0.075775
18
36
0.04922
0.060002
18
72
0.058525
0.041778
18
108
0.045035
0.020357
18
144
0.02728
0.016545
18
162
0.02057
0,011974
18
180
0.01624
0.009968
18
216
0.004095
0.004536
18
252
0.000635
0.001181
18
288
5e-06
2.2e-05
18
306
0.0
0.0
18
315
0.0
0.0
18
323
0.000965
0.004269
18
324
3.5e-05
6.7e-05
18
325
0.00613
0.027297
18
342
5e-06
2.2c-05
18
360
3e-05
0.000134
Figure 18: Data used generate Figure
For this experiment n 500, and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
43

---

mean
std. dev.
20
20
0.222785
0.087655
20
40
0.103795
0,062048
20
80
0.085645
0.040937
20
120
0.06505
0.023917
20
160
0.037505
0.014094
20
200
0.027705
0,013622
20
220
0.02015
0.009954
20
240
0.0129
0.007192
20
260
0.00727
0.004
20
280
0.005775
0.003874
20
300
0.001783
0.001685
20
340
0,000275
0.000197
20
360
4.5c-05
5.1c-05
20
380
0.0
0.0
20
390
0.0
0.0
20
399
6.5e-05
0.000208
20
400
0.005205
0.023042
20
401
0.000145
0.000417
20
420
0.0
0.0
20
440
0.00019
0.00085
Figure 19: Data used to generate Figure For this experiment 500, and the maximum number of iterations of ALS was 100. The reported values are aggregated over 20 independent trials.
r
mean
std. dev.
20
20
0.239725
0.102431
20
40
0.13363
0.059243
20
80
0.096775
0.033897
20
120
0.0835
0.029776
20
160
0.044465
0.01832
20
200
0.02991
0,01427
20
220
0.024735
0.011906
20
240
0.01598
0.00924
20
260
0.011645
0.008376
20
280
0.00604
0.004469
20
300
0.002445
0.002042
20
320
0.00157
0.001794
20
340
0.00025
0.000173
20
360
5e-05
5.1e-05
20
380
0.0
0.0
20
390
0.0
0.0
20
399
7.5e-05
0.000251
20
400
0.001155
0.004456
20
401
0.0001
0,000296
20
420
2c-05
8.9e-05
20
440
0.0
0.0
Figure 20: Data used to generate Figure 10
For this experiment n. = 1000, and the maximum number of iterations of ALS 20. The reported values are aggregated over 20 independent trials.
44

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We provide rigorous proofs of all the statements made in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
45

---

Justification:
We clearly describe the assumptions under which our conclusions hold in all theorem statements.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the assumptions under which our conclusions hold and provide rigorous proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We clearly describe how the experiments can be reproduced.
Guidelines:
46

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide python code to run both experimental setups as part of the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.ccppulic//guus http://icc/giiie////eeeuubiiibii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
47

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We don't have training/test experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The error bars clearly describe the statistical significance using standard visualization techniques
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We used a regular laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
48

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps:/nauurips.c http:///arrrr...cooooo.ll.ataaaa
Answer: [Yes]
Justification: The research conducted in the paper conforms, every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work has foresceable societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
functioning correctly, harms that could arise when the
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
49

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We properly credit original owners assets.
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
We don't releas new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
50

---

Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non stanndaddrrd components.
Please refer to our LLM policy for what should or should not be described.
51


Reviews:
[{"review_id": "gjcyasiXwZ", "reviewer": "Reviewer_JGuV", "summary": "This paper analyzed the algorithm of ALS (Alternating Least Squares) with overparameterization for the symmetric low-rank tensor decomposition problem. It was proved that when the overparameterized rank $k \\\\gtrsim r^2$ ($r$ is the rank of the tensor), randomly initialized ALS converges in two iterations to an approximate optimum. The main ingredient of the proof is a careful analysis of random initialization, in particular, several anti-concentration properties of Gaussian matrices. The paper also included some experiments to discuss whether the $O(r^2)$ dependency is necessary.", "questions": "Please refer to the Weaknesses part.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The result appears novel and is a welcomed contribution to the study of low (CP-)rank tensor decomposition. Though I have not checked all the details in the proof, I did a few sanity checks and did not find obvious flaws. The experimental results on parallel and sequential ALS are also interesting. I think the paper is overall acceptable. \n\nSpeaking of weaknesses, one issue is that the error bound is proven for $X^{(1)} \\otimes Y^{(1)} \\otimes Z^{(2)}$, rather than $X^{(2)} \\otimes Y^{(2)} \\otimes Z^{(2)}$. It would be helpful to discuss if anything can be proved for later iterations. Will the error diminish or accumulate?", "was_revised": true, "final_justification": "The author has answered my question, and I have no particular problem with this paper right now. I will keep my positive score.", "rebuttal": "We thank the reviewer for their kind comments about the novelty and significance of the results. The question about the error in later iterations is a nice question, and from a technical standpoint it is related to some of the differences between standard ALS and the parallel version we analyze. Our argument does not imply such a decay in the error, and this seems beyond the scope of our current techniques as far as we can see."}, {"review_id": "RDX047kCQU", "reviewer": "Reviewer_L37m", "summary": "This paper discusses the accuracy of alternating least squares for tensor decompositions under the overparameterized setup. For a third order tensor $n\\times n \\times n$ with CP rank $r$, this work shows that ALS overparameterized with rank $r$ achieves global convergence with high probability under random initialization.", "questions": "n/a", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The introduced bound of $O(r^2)$ is much better than the previous work of $O(r^{7.5})$ and is impressive.\n\nWeaknesses: One major weakness of this work is its presentation. As a theoretical study without experimental results included in the main text, readers will expect a more detailed algorithmic analysis and rigorous proofs. However, this work only provides a brief sketch of the analysis on pages 8 and 9, with many important analysis missing. Detailed comments are presented below:\n1. lines 262-264: \"suppose Y^t and Z^t were each drawn independently and randomly from colspan(A), with high probability $colspan(A\\otimes A) \\subseteq colspan(X^t\\odot Y^t)$\": this statement is nontrivial, it would be good to include the reference if this has been proved in the previous work, or provide a formal theorem with (sketched) proof.\n2. Line 268: \"Of course, the columns of X and Y are not initialized randomly in the span of A, instead they are random in the whole n-dimensional space.\" one important part that is missing is to show that with $k=\\Omega(r^2)$, the subspace spanned by $A$ will be in the subspace of $X,Y,Z$ that are randomly generated with high probability. \n3. Line 275: \"The first step of ALS (Algorithm 1, Line 8) will set Z so that the second term is 0, which since X and Y are randomly initialized means setting $Z^{\\perp}=0$\": as this step is fixing X, Y and update Z with solving a least squares problem, maybe it's better to direct explain in the matrix format rather than keeping the CP format.\n4. Line 283: \"Thus, proving (4) reduces to showing that $X^1 \\odot Y^1$ has rank $r^2$\": this statement is nontrivial, it would be good to provide a formal theorem with proof.\n5. It’s unclear how to derive the equation below 294, and why is it important.\n\n\nNit: in line 261, \"where in the first line $\\langle\\cdot\\rangle$ denotes the linear span, and in the second line $\\odot$\" should be \"...,  in the second line $\\odot$ represents a Khatri-Rao product\".", "was_revised": true, "final_justification": "Raise the score as the rebuttal provided by the authors clear a couple of my concerns. This is a great contribution, but it would be good for authors to improve the clarity in the main text of the work.", "rebuttal": "We thank the reviewer for their feedback and highlighting the significant improvement in the amount of overparametrization. \n\nWe thank the reviewer for their suggestions to improve the presentation, and we will clarify the questions asked in the final version. However, we would like to take this opportunity to clarify some confusion or potential misconceptions. We emphasize that all our claims are rigorously proven in the appendix. The analysis is technically quite involved and does not fit fully within the page limit. In the main body of the paper, we prioritized giving the main intuition by highlighting different challenges in proving the main result and giving a sketch of the main ideas involved, as is the norm in many learning theory papers with technical proofs. The full ArXiv version will include all the proofs in the main body. Now we address some of the specific questions: \n\n “lines 262-264: \"suppose $Y^{(t)}$ and $Z^{(t)}$ were each drawn independently and randomly from $\\mathrm{colspan}(A)$, with high probability...\": this statement is nontrivial, it would be good to include the reference or proof”” \n\nThanks for the question. The confusion comes from a typo in the sentence.\nHere, the $Z^{(t)}$ should be replaced by $X^{(t)}$. We hope that this clarifies the confusion. Taking that into consideration, the statement is a non-trivial statement about the Khatri-Rao product of random vectors in a subspace (which is actually implied by the much stronger statement in Theorem 4.1). However we emphasize this sentence was merely a hypothetical that was only meant to illustrate the technical challenge. The key point is that such an assumption (about the initialization being random in the $\\mathrm{colspan}(A)$ ) cannot be made and our analysis does not rely on this statement in any way. We will correct the typo, and emphasize the above point in the final version. \n\n “one important part that is missing is to show that with $k=\\Omega(r^2)$, the subspace spanned by $A$ will be in the subspace of  $X, Y, Z$ that are randomly generated with high probability.” \n\nThere seems to be some misconception here that we would like to clarify. This is not what our proof approach involves; in fact, this should not be expected to be true. For the interesting regime of parameters for r and k, with high probability the spans of the randomly initialized X and Y will have trivial intersection with the column span of A. Here the ALS iteration plays an important role. In fact we prove that after we update X and Y in one iteration of the ALS algorithm, they will be in the subspace spanned by A (this is a statement that follows directly from the expressions of $X^{(1)}$ and $Y^{(1)}$ as the least squares solutions for the problems) but most importantly that $X^{(1)}\\odot Y^{(1)}$ spans the subspace spanned by the columns of $A\\otimes A$. This is a non-trivial statement.\n\n “Line 283: \"Thus, proving (4) reduces to showing that $X^{(1)}\\odot Y^{(1)}$ has rank $r^2$\": this statement is nontrivial, it would be good to provide a formal theorem with proof.“\n\nAs mentioned already, $X^{(1)}$ and $Y^{(1)}$ ($X$ and $Y$ after the first ALS update) will both be in the subspace spanned by the columns of $A$, this in particular means that $X^{(1)}\\odot Y^{(1)}$ will be in the column span of $A\\otimes A$. Thus proving that the rank of matrix $X^{(1)}\\odot Y^{(1)}$ has rank $r^2$ together with the fact that its columns lie in the subspace spanned by $A \\otimes A$ implies that the columns of $X^{(1)}\\odot Y^{(1)}$ must span the entire space of $A\\otimes A$. We will clarify this in the revised version. \n\n“It’s unclear how to derive the equation below 294, and why is it important.”\n\nUsing a standard identity for the Khatri-Rao product (equation (3) in the paper) the matrix $\\hat{X}\\odot \\hat{Y}$ can be written as $(A\\otimes A)$ times the matrix below line 299. Using that A is well conditioned (its least singular value being lower bounded), it follows that $A\\otimes A$ is also well conditioned using standard multiplicative properties of singular values. Hence arguing about the least singular value of the matrix below line 299 suffices to show our result. As mentioned earlier, we chose to highlight the crucial steps of the proof in the proof overview due to space limitations. The full details of the proof are in the appendix.\n\nTo reiterate, we thank you for the questions/ comments. While all of the above technical details and the entire proof are in the appendix, your questions help us by identifying portions of the overview that we can clarify or emphasize better. Please let us know if there are any remaining questions/ clarifications."}, {"review_id": "SvkSCkRaUN", "reviewer": "Reviewer_sE4m", "summary": "This paper provides a new analysis for a commonly used method, alternating least squares (ALS), for computing the CP decomposition of an order-3 tensor. Computing a decomposition with minimal rank can be computationally intractable. An alternative approach is to compute a decomposition with higher rank (but hopefully not too high). This paper shows that with high probability, under random initialization, targeting a rank $k = O(r^2)$ is enough, where $r$ is the actual CP rank.", "questions": "**Note:**  In general, my opinion is that a conference paper should be reviewable based on the main body of the paper given the limited time to do multiple reviews.\n\nIt is a great academic tradition to have questions which are more of a comment.\n\n* I believe the author(s) should amend the title to reflect that the results hold only for CP decompositions. As it stands, the title is misleading since there are many kinds of tensor decompositions.\n\n* The reference to Hillar and Lim (2013) is incorrect in the references: It appeared in JACM. While I did not check the entire bibliography, this kind of basic error suggests that the authors should check their references more carefully.\n\n* I was surprised that there was no reference to Håstad's (famous) 1990 paper on the hardness of tensor rank over $\\mathbb{Q}$. The Hillar and Lim paper contains a lot of discussion on the model of computation and relationship between rank over different fields.  There is comparatively little discussion here: perhaps a sentence to clarify would help.\n\n* While improving the sufficient rank for admitting a decomposition, is there any hope for lower bounds? Perhaps this could be an interesting question for future work.\n\n* The main technical result in the paper is in Theorem 4.1 and actual bound on the probability of the relevant event comes from the Carbery-Wright inequality. Since this is a result about a particular estimator and not a more general statement about singular values of Khatri-Rao products, is it possible to extract a lemma which could be of use elsewhere?\n\n* The fact that any experimental evidence was left to the supplement and *not even mentioned in the main paper* is a red flag for me. Sneaking them \"in the back door\" through the supplement is, in my opinion, a violation of ethical norms. The overall research direction would surely benefit from careful experiments. However, simply running experiments on various flavors of ALS and not other methods (gradient descent, tensor power method, etc.) is not a proper experimental design. The authors should remove the experiments and leave practical evaluation to future work.\n \nSome minor suggestions:\n\n* (line 192) I found the \"polynomial time\" and \"$O(1)$ steps\" combination a bit confusing. What are the parameters of interest and which ones are going $\\to \\infty$ in these statements should be clarified. I understand this is coming from the black-box linear system solver but the statement could be clearer.\n* Relatedly, please provide a standard reference for the solver you use.\n* (p2) \"mildly conditioned\" is a little vague on a first reading. Perhaps make it a little more specific?\n* Why state the result for the symmetric case and not the general case?\n* (line 288) \"Gaussianand\" --> \"Gaussian and\"", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n* The new analysis opens the door to the analysis of ALS for other decompositions.\n* The technical lemma may have uses in other applications involving optimization over tensor spaces.\n\n**Weaknesses:**\n\n* There is some gap between what the paper claims and what the results appear to be.\n* The experiments are inadequate (but not needed).", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback and comments. We will implement the changes that you proposed. We will also update the bibliography more carefully; thank you also for suggesting that we cite the work of Hastad.\n\n For the experiments, our intent was not to claim that ALS is superior to other existing methods for tensor decompositions. As you pointed out, the main contribution of our work is the theoretical analysis under overparametrization; we hope these techniques also extend to other iterative methods under overparameterization. Hence we chose to focus solely on the theoretical portion for the main body of the paper. The main purpose of our experiments was to bring attention to what we think is a particularly interesting question about the extent of overparametrization needed for global convergence of ALS and its variants. This is directly related to one of the questions you posed about lower bounds on the rank of the decomposition. Our analysis suggests that $O(r^2)$ overparameterization suffices (we prove this for the parallel variant). Our experiments suggest that sufficient overparameterization (potentially even up to $\\Omega(r^2)$ ) may be necessary as well (the experiments are most definitive for the parallel variant); proving such lower bounds seems quite challenging and interesting in its own right. We think this would be an interesting direction for future work. To your point, we do not intend our experiments to be taken as an evaluation of (either variant of) ALS as a method, and such evaluations require thought and care.  We appreciate you pointing this out, and we will make this point more clear in our revision."}, {"review_id": "3inAuO2ssW", "reviewer": "Reviewer_JdA9", "summary": "ALS-lke method (which would be more correctly called Paralles Least Squares) to the problem of decomposing a 3-way tensor into CP format is considered. It is assumed that all elements of the original tensor are known and it is small enough to fit in the computer memory; also it is known that the tensor is of $\\epsilon$-$r$-CP-rank. The paper establishes that when decomposing into CP format of overparametrized rank $O(r^2)$ using the new method with random (Gaussain) initialisation of cores presented by the authors, one can achieve convergence guarantees with high probability and a given accuracy.", "questions": "- Could your proof method have been extended to regular ALS?\n- Could your proof method have been extended to the case of rank $k<r^2$ (or $k<r^{d-1}$  in general)?\n- Could your proof method have been (non-trivially) extended to the case of tensors of higher dimension?\n- What is the practical conclusion of your algorithm, why a new method is needed if for $k=r^2$  overparametrized CP decomposition if the latter can be constructed trivially?\n- Can you somehow round your resulting decomposition to get a decomposition with lower rank (but possibly higher error)?\n- Why explore CPD when there are other tensor decompositions that are much better in the above context (obtaining almost exact rank), e.g. for Tensor-Train we can get an overparametrized decomposition, but then round it to the desired rank?", "limitations": "The limitations are listed in the paper and my review: only 3D tensors, only the new algorithm is considered, and the entire tensor is already set with its elements.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "__Strength__\n\n- The article is well written, easy to read, the main claims are there in the text, the technical details have gone to Appendix.\n- All major assertions are rigorously proven.\n\n__Weakness__\n\n**New algorithm** \nOne of the main weaknesses -- the paper uses its own (rather than the standard ALS) method to construct the decomposition. In fact, if the given tensor $\\mathcal T\\in\\mathbb R^{n_1\\times n_2\\times n_3}$ is known to be CP-rank $r$ (or $\\epsilon$-$r$, i.e. can be represented with CPD of rank $r$ with accuracy $\\epsilon$), then the construction of its CPD of rank $r^2$ is trivial. I will show that. For such a tensor all matricizations have rank $r$ (or $\\epsilon$-rank), i.e. we can use (truncated)-SVD to obtain the decomposition of the first matricization: $T_1=$reshape($\\mathcal T$, $n_1$, $n_2n_3$) = $U\\Sigma_1V_1^T$, where $U\\in\\mathbb R^{n_1\\times r}$. Similarly for the last matricization: $T_3=$reshape($\\mathcal T$, $n_1n_2$, $n_3$) = $U_3\\Sigma_3V^T$, where $V\\in\\mathbb R^{n_3\\times r}$. Note the property of nullspace of $U$ and $V$: if $U^Tx=0=\\sum_iU[i,j]x[i]$, then $\\sum_iT[i,j,k]x[i]=0$, and similarly for $V$. Consider a 3-way core tensor $\\mathcal G=\\mathcal T\\times_1U\\times_3V=\\sum_{i,j}\\mathcal T[i,:,j]U[i,:]V[j,:]\\in\\mathbb R^{r\\times n_2\\times r}$. After swapping the dimensions and matricization of this tensor, we obtain the matrix $G=$reshape($\\mathcal G'$, $n_2$, $r^2$). Now let $c_1=U\\otimes 1_r\\in\\mathbb R^{n_1\\times r^2}$, where $\\otimes$ is the Kronecker product and  $1_r\\in\\mathbb R^{1\\times r}$ is the vector of length $r$ containing ones. Similarly, let  $c_3=1_r \\otimes V\\in\\mathbb R^{n_3\\times r^2}$. Finally, remembering that matrices $U$ and $V$ have orthogonal columns: $U^TU=V^TV=I_r$ (and properties of their nullspaces), we obtain that for all admissible $i$, $j$, $k$, the following is true (or approximately true with accuracy $\\epsilon$): $\\mathcal T[i,j,k]=\\sum_{\\alpha=1}^{r^2}c_1[i,\\alpha]G[j,\\alpha]c_3[k,\\alpha](=\\sum_{\\alpha_1}^r\\sum_{\\alpha_2}^rU[i,\\alpha_1]\\mathcal G[\\alpha_1,j,\\alpha_2]V[k,\\alpha_2])$. Thus, we obtained an exact (in the case of exact ranks) decomposition of the original tensor into a CP format of rank $r^2$, and directly, without iterations. Moreover, this decomposition is obtained under milder conditions on the original tensor: it is sufficient that only two matricizations are of rank $r$, rather than the stricter condition in the paper at hand that the CPD $\\mathcal T$ is of rank $r$, from which it follows, in particular, that all matricizations must be of rank no greater than $r$.\n\n**Scalability**\nIn this paper tensors of dimension 3 considers only. For a tensor of arbitrary dimension $d$, which is known to have CPD of rank r, one can trivially (by the method described above) obtain the CP decomposition of rank $r^{d-1}$ directly. However, such tensors are not considered in the paper. Studying the proofs of the theorems led me to the idea that when extending the methods used by the authors to tensors of arbitrary dimension, the same estimate on the rank of the overparametrization is obtained (indeed, the authors talk about the total dimension of the columns of the cores of the decomposition except for the the one for which a local iteration is currently in progress, and since this dimension is a Kronekker product of the individual columns, it will be equal to $r^{d-1}$). In contrast, for example, the paper [1] (cited as SWZ19), which the authors try to generalise, studies tensors of common dimension (and obtains an estimate on the overparametrized rank $O((r/\\epsilon)^{d-1})$ ). In the paper [2]  (cited as WWL+20) similarly, the result is obtained for the general case of d-way tensors (namely, the rank estimate is given as $O(r^{2.5d}\\log n)$ for gradient descent algorithm).\n\n**Practical relevance**\nThus, it is not very clear to me why one would want to study the properties of a new (iterative) algorithm that shows the same results as a naive direct algorithm. Furthermore, the authors restrict themselves to the case of 3-way tensors. Important cases where the dimensionality of the tensor is much larger, or the important problem formulation where we do not have all the values of the tensor but only a part of them (the so-called tensor completions problem), are not considered. The practical value of these results is questionable.\n\n**Numerical Results.**\nIn Appendix, the authors present numerical experiments on synthetic data. It turns out that the standard ALS converges better than the presented algorithm. Moreover, it turns out that if the rank is at least 1 less than $r^2$, the presented new algorithm does not converge to almost zero error. It would be interesting to prove this behaviour in general, but it is not proved. On the contrary, the standard ALS behaves better even for overparametrized rank values smaller than $r^2$ (see figs. 3--10). And it is precisely this behaviour of ALS that is important to study from a practical point of view. Besides, it is important to know how ALS behaves not on absolutely random data (but, for example, on sparse data, or taken from real-world dataset). It is also important to study ALS convergence not on random cores initialisations, but, for example, with HOSVD. None of the above is mentioned in the article.\n\n**Other tensor decomposions**\nThe motivation for choosing exactly the CP decomposition for the purposes in the paper is not clear. There are many other tensor decompositions. For example, for the Tensor-Train decomposition there is a method for its constructing (so-called TT-cross approximation method), which gives also overparametrized rank, and for which there are guarantees ([3]). In this case, the obtained overparametrized TT-decomposition can be later rounded off to a decomposition with a smaller rank [4].\n\n[1]. Zhao Song, David P. Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In Symposium on Discrete Algorithms (SODA), 2019\n\n[2]. Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-parameterized tensor decomposition. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21934–21944. Curran Associates, Inc., 2020.\n\n[3]  Stanislav Budzinskiy, Nikolai Zamarashkin. Tensor train completion: Local recovery guarantees via Riemannian optimization, 2023.\n\n[4] I. V. Oseledets. Tensor-train decomposition. SIAM J. Sci. Comput., 33(5):2295–2317, 2011\n\nMinor ans suggestions\n\n\n- L129 ALS does not face some **fo** the earlier issue\n- L261L \"where in the first line $<\\cdot>$ denotes the linear span, and in the second line $\\otimes$\" 1) The sentence is cut short 2) The notations has already been introduced\n- L174--175 : flatten -> better use `reshape`\n- L275 : (Algorithm 1, Line 8) Line **16**?\n- L288 Gaussiansan\n- L292 o(1). Usually O(1) is used to denote the constant (which does not depend on anything). o(1) implies that this value tends to zero. However, it is not clear at what limit it tends to zero. It is better to give more detailed asymptotics.\n- It is better to use three separate characters for outer, Kronecker and Khatri-Rao products.\n- Better use logscale on error plots", "was_revised": true, "final_justification": "*   I recognize the **significant theoretical challenge** overcome: proving convergence guarantees (from random initialization, with high probability) for *any* iterative method applied to CP decomposition requiring only *polynomial* overparametrization (O(r²)) is a non-trivial result. \n*   The paper is well-written, and the technical analysis appears sound for the specific algorithm and setting (3D tensors, rank O(r²)).\n\n\n\nThe effect and importance of this point are limited by these things:\n1.  The sole focus on $d=3$ limits how it compares and can be used versus prior studies claiming results for general $d$.\n2.  The use of a non-standard algorithm whose empirical work is shown to be worse than standard ALS calls into question the practical significance of the results.\n3.  Unresolved questions about if the methods can be used for standard ALS, lower ranks, or higher dimensions.\n4.  A lack of work on real uses (real data, completion, rounding) and not enough reason for focusing theoretical work on CP decomposition given its real-world limits and other choices available.", "rebuttal": "We thank the reviewer for the detailed feedback. We would like to respectfully push back on the main motivation for this work. As we also mention in our paper, there are indeed other existing polynomial time algorithms that find decompositions of rank $r^2$. Most of these methods (including the one suggested by the reviewer) involve singular value decomposition (SVD) or variants to find the span of the factors. We remark that this is mentioned early in the paper; see lines 75-77 including references to BCV2014 and SWZ2019. \n\nInstead, the main motivation of our work is to analyze popular iterative heuristics for non-convex optimization. Tensor decomposition is seen as a canonical non-convex optimization problem, that is a stepping stone to more complex non-convex optimization problems that frequently arise in machine learning. This is exactly the  motivation behind the important work of Rong Ge, Jason Lee, Tengyu Ma, Xiang Wang, Chenwei Wu (published in NeurIPS 2020) that analyzes gradient descent for tensor decomposition; in fact they require an overparametrization of around $r^{7.5}$ which is much worse than the $r^2$ for more sophisticated SVD-based approaches (and even incur extra logarithmic factor in the ambient dimension n). In comparison our work analyzes a (parallel) variant of ALS, the most popular iterative heuristic for tensor decomposition; in general, this falls under the class of block-coordinate descent methods, another popular heuristic for optimization problems. We prove that a rank of $O(r^2)$ suffices (we are unaware of any such result for ALS-type methods). Admittedly we analyze a slight variant of the most popularly used ALS method but we hope that our techniques can be extended in future work to give theoretical guarantees for the standard ALS method. Providing theoretical guarantees for popular iterative methods involves significant technical challenges (over SVD-based methods) which we outline and overcome in this work. Note that the work of Ge and others also had to contend with many such challenges as well (and also analysed a variant of gradient descent). Such theoretical analyses of iterative heuristics are already interesting for tensor decomposition. But they become even more exciting from the broader perspective of non-convex optimization; we hope that they may reveal insights into the optimization landscape and that these ideas translate to other non-convex problems. I hope this conveys our main motivation, and why this  research direction is interesting;  this interest also seems to be reflected in the excitement of the other positive reviews. \n\nWe agree that it would be interesting to extend our techniques to higher order tensors, and we leave this for future work. We suspect that these techniques should help; nevertheless decomposing order 3 tensors is already a computationally difficult non-convex problem and to the best of our knowledge few theoretical guarantees were shown for iterative methods even in this setting."}, {"review_id": "I9G4bIElsJ", "reviewer": "Reviewer_mBVm", "summary": "This paper proves that alternating least squares (ALS), when initialized randomly and overparameterized to $k=O(r^2)$, achieves global convergence with high probability for decomposing and approximating a third-order tensor of rank $r\\ll n$. The main contributions are: 1. ALS with moderate overparameterization ($k = O(r²)$) ensures global convergence; 2. theoretical guarantees apply to both tensor decomposition and low-rank approximation; 3. Novel analytical tools are developed to study convergence in overparameterized settings.", "questions": "1. What is the minimal achievable value of $k$ for your guarantees? Is overparameterization fundamentally necessary to ensure theoretical guarantee for ALS, or could alternative approaches work without overparametrization? \n2. What key techniques enable the improvement from prior overparameterization bounds $(k=O(r^{7.5\\log n}$) to your result ($k=O(r^2)$)? Could you elaborate on how this reduction is achieved and why $k=O(r^2)$ is the threshold for your analysis?\n3. Does Theorem 2.2 require the error term $E$ and the tensor $T$ to be symmetric? Or does the result hold under weaker structural assumptions?\n4. A key distinction between matrix and tensor rank is that the factors $A,B,C$ in tensor decomposition may be rank-deficient. Your analysis assumes full-rank factors with bounded condition numbers — does this restriction simplify the proof, or could the results be extended to rank-deficient cases?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Improved Global Convergence Guarantees: The work establishes that ALS with moderate overparameterization ($k=O(r^2)$) achieves global convergence, a significant improvement over prior results requiring much larger $k$.\n2. Broad Applicability: Theoretical guarantees extend beyond exact tensor decomposition to the more general low-rank approximation problem.\n3. Novel Analytical Techniques: The analysis introduces innovative tools, such as matrix anticoncentration arguments, to study convergence in overparameterized settings.\n\nWeaknesses:\n1. Justification for Overparameterization: The necessity and sufficiency of the $k=O(r^2)$ requirement in the proof remain unclear. A deeper discussion on whether this bound is tight or merely an artifact of the analysis would strengthen the work.\n2. Restrictive Well-Conditioned Assumption: The assumption that factors $A,B,C$ are well-conditioned excludes many realistic tensors and significantly simplifies the theoretical analysis. Extending the results to ill-conditioned or rank-deficient cases would enhance practical relevance.", "was_revised": true, "final_justification": "I appreciate the theoretical contributions of the paper and continue to support it. My rating remains unchanged.", "rebuttal": "We thank the reviewer for the positive feedback and kind comments on the novelty of our techniques\n\n\nIn terms of overparameterization, our experiments (included in the appendix) suggest that $r^2$ overparameterization is indeed necessary for the parallel version of ALS that we analyze to succeed.  For standard ALS, our experiments indicate that some degree of overparameterization is definitely necessary (and maybe even $\\Omega(r^2)$), though it is less clear to what degree.  Both of these experimental observations hold even in the setting when $A, B, C,$ are generated randomly.  We think it is a very interesting direction of future work to analyze what degree of overparameterization is necessary for ALS to succeed.  That is, we provide an upper bound for parallel ALS, can one prove a lower bound on the overparameterized rank?\n\nThe overparameterized rank being $r^2$ comes from the key observation that the slices of the tensor lie in a Khatri-Rao space of $A \\odot A$ of dimension r, which is a subset of the larger Kronecker space $A \\otimes A$ of dimension $r^2$.  At a high level, the Khatri-Rao space is very sensitive to the basis (columns) of $A$, whereas the Kronecker space $A \\otimes A$ only depends on the subspace spanned by the columns of $A$, and not the individual basis vectors.  Thus, it is somehow an easier space to recover.  The main work in our analysis is in showing that this $A \\otimes A$ space is indeed recovered by the iterates.    \n\nThe question about the full rank (or condition number) assumption of $A, B$ and $C$ is a very interesting question. It seems quite likely that if we make extra assumptions (e.g., some gap between the significant singular values and small singular values), we may be able to leverage the robust guarantee for low-rank approximations to move the projection onto the small singular vector directions onto the error term. However, this does not seem to work in general. \n\nIn the main body, we sketched the proof assuming that the tensor $T$ and error matrix $E$ are symmetric, for ease of notation and also to convey the intuition of the proof.  Our theorems and proofs in the appendix extend to the asymmetric setting."}]

Author rebuttal:

Meta-review: The paper analyses the popular alternating least squares (ALS) algorithm for CP tensor decomposition. The paper shows that ALS converges to the global optima if there is sufficient overparameterization: if the tensor has rank r, then ALS with O(r^2) factors converges to a factorization with 0 error. This improves on results of WWL+20 who showed that a variant of gradient descent converges to the global optima with overparameterization O(r^7.5).

The reviewers made some suggestions to improve the writing, and I recommend the authors carefully implement the changes in the final version. There was also a comment about potentially changing the title. On my end, I am okay with the current title for similar reasons to what the authors mentioned, but if the authors prefer to change the title that is fine as well.

Another concern raised was the the paper analyses a variant of ALS. The modification updates all the factors A, B, C in parallel, using their values at the previous iteration, instead of say using the updates value of A to perform the update for B. I consider this modification to be pretty benign in the context of doing modifications to iterative techniques to analyze them.

ALS is by far the most popular algorithm for tensor decomposition, and tensor decomposition has also served as a canonical setting to understand non-convex optimization methods. The paper makes significant contributions to understanding optimization techniques for the problem. There are also some interesting future questions raised here by the reviewers, in particular on the need for overparameterization, and if lower bounds are possible here (the experiments suggest some overparameterization may be necessary). Investigating this further would be very interesting.

--other comments--

The paper is missing citations to some previous work like the following on analyzing ALS for CP decomposition, please correct it:

- Local Convergence of the Alternating Least Squares Algorithm for Canonical Tensor Approximation
- On the Global Convergence of the Alternating Least Squares Method for Rank-One Approximation to Generic Tensors
- Provable Tensor Factorization with Missing Data
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates
Decision: Accept (spotlight)