Guarantees for Alternating Least Squares in Overparameterized Tensor Decompositions

We thank the reviewer for the positive feedback and kind comments on the novelty of our techniques

In 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?

The 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.

The 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.

In 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.

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.

Instead, 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.

We 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.

Thank you for your detailed response. I appreciate the authors' added clarity about why they analyzed iterative heuristics in non-convex optimization. I remain unconvinced that the paper warrants a much higher score. My concerns stem from specific limits in the study's scope and real-world use, which the response did not fully address.

Key Concerns:

1. Limited Scope of Dimensions & Misleading Comparison to Previous Studies:

   • The results in the paper are limited to 3-way tensors. The authors admit that expanding the analysis to higher dimensions ($d > 3$) is a complex task for the future.
   • This limit greatly lessens the perceived advance over prior studies. The authors state that WWL+20 needed overparametrization of $O(r^{7.5})$ for $d=3$ (compared to their $O(r^2)$), but WWL+20 had results for general d-way tensors. Likewise, SWZ19 offers a bound $O((r/ε)^{d-1})$ for general $d$. Thus, the paper's work is an isolated result for $d=3$, not a generalization. It is misleading to claim an advance over these studies without noting this major dimensional limit, as $d=3$ is often less useful than higher-dimensional settings in real uses. The exponential advance over WWL+20 for $d=3$ is noted, but its effect is lessened by this limit.

2. Algorithm Selection and Gap in Real-World Use :

   • The response makes a solid point that studying iterative methods (like this version of ALS) for basic non-convex problems (like CP decomposition) is theoretically interesting per se, separate from giving the most practical decomposition method. I acknowledge this motivation and the inherent theoretical challenge in proving convergence guarantees for iterative methods from random initialization. This distinction between algebraic existence and iterative convergence is a valid contribution.
   • Yet, considering a non-standard ALS (Parallel Least Squares) instead of the common used standard ALS is still a major weakness. The authors hope their methods can apply to standard ALS, but this is only a guess now. Also, the experiments show that standard ALS is better than the proposed method empirically, even for ranks below $r^2$. This makes a disconnect: the theoretical guarantees are for an algorithm that is empirically worse than a standard one on the very problem being studied. Showing that these guarantees affect how standard iterative methods work in practice is key.

3. Unaddressed Technical Scope and Real-World Worth:

   • Unanswered Questions: Questions about expanding the proof method to standard ALS, to ranks $k < r^2$ (where standard ALS does better empirically), or to $d>3$ are still unanswered. The response focuses on rationale but does not handle these limits of the work now.
   • Rationale for CP: CP is a basic non-convex problem, but the response does not fully explain why it was chosen over other unstable formats or why theoretical guarantees for CP decomposition are so helpful, given its known practical issues (ill-posedness, sensitivity) and more dependable choices (like Tensor Train) with stable algorithms and convergence guarantees. The historical role is clear, but a better reason for its ongoing theoretical study in this context would help the paper.
   • Limited Study of Real Uses: The numerical experiments only use synthetic random data and compare it to ALS. There is no work with real-world data, sparse tensors, tensor completion (missing data), or the important step of rounding the overparametrized $O(r^2)$ decomposition to a lower rank -- a common thing done with other decompositions like TT. The practical worth and dependability of the method are unclear.

Overall:

The effect and importance of this point are limited by these things:

1. The sole focus on $d=3$ limits how it compares and can be used versus prior studies claiming results for general $d$.
2. 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.
3. Unresolved questions about if the methods can be used for standard ALS, lower ranks, or higher dimensions.
4. 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.

The theoretical analysis for the setting is valid and the reason for studying iterative methods is accepted, but these limits stop me from raising the score much. The work is a key but specific theoretical step; making its scope wider or showing clearer real-world use or if it can be used for standard algorithms would greatly raise its effect. Thus, I rise my score to 4 (Borderline accept).

Regarding the limitation on $d=3$, we will make sure to emphasize that our comparison with the work of Ge et al is only valid for $d=3$ to avoid confusion. We believe that it is possible that a generalization of our techniques could give a bound of $O(r^{d-1})$ for higher order tensors. At a technical level, one would have to show a generalization of Theorem 4.1, namely that (for order 4 tensors for example, with matrix variables X,Y,Z and W) $\sigma_{r^3}(\hat{X}\odot \hat{Y}\odot \hat{Z})\geq \frac{1}{\mathrm{poly}(n,k)}$. It is quite likely that our arguments can be extended to show this, it would however require overcoming challenges due to limited independence of matrices $\hat{X}, \hat{Y}$ and $\hat{Z}$. We would also like to note that the 3rd order case is itself interesting, and there are other works in the literature that focus entirely on order 3 tensors (e.g. [Sharan, Valiant 2017]: Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use, [Ge Ma 2015]: Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms)

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.

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.

We thank the reviewer for their feedback and highlighting the significant improvement in the amount of overparametrization.

We 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:

“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””

Thanks for the question. The confusion comes from a typo in the sentence. Here, 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.

“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.”

There 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.

“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.“

As 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.

“It’s unclear how to derive the equation below 294, and why is it important.”

Using 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.

To 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.

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.