Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: A connection is established between gradient descent in an over-parameterized symmetric CP decomposition and a corresponding tensor deflation process. In particular, a gradient-based learning algorithm is introduced which admits a probabilistic convergence guarantee, as well as an analysis characterizing the overlap between the learned tensor and various low-rank components of the original (orthogonally decomposable) tensor.
main_review: The current paper is one of many works giving rigorous bounds on the correctness of gradient-based learning in different linear-algebraic settings, and does a good job of clearly positioning these new results within this growing area of research. The main novelty here is a characterization of the trajectory of the learned tensor, which is shown to exhibits a strong similarity with tensor deflation methods (such as the tensor power method of [Anandkumar et al., 2014]). Although the results and methods are quite technical, the paper is well-written, and the presentation makes the high-level takeaways of the results apparent to non-experts.

That being said, I have a few suggestions for how the authors could improve the manuscript. First, it would be helpful to give a more thorough comparison with [Wang et al. 2020], which has significant overlap with the current work. While a brief comparison is given in the paper, it would be useful to expand on this further. 

Secondly, the authors' findings seem very similar in nature to the seminal work of [Saxe et al. 2013, "Exact solutions to the nonlinear dynamics of learning in deep linear neural networks"], wherein a deep linear neural network trained by gradient descent was shown to capture progressively larger singular values of a target matrix. Although the methods used are completely different from the current work, the final results exhibit strong qualitative similarities, especially considering the connection between singular values of a matrix and magnitudes of the components of an orthogonally decomposable tensor. If the authors see any merit in this connection, it would be useful to mention it to readers.

Finally, could the authors comment on the restriction to fourth-order tensors in the paper? While the restriction to orthogonally decomposable tensors seems to be necessary to attain the main results, it isn't clear why only fourth-order tensors were studied. It would be useful to readers to indicate in the manuscript whether or not the results could be easily generalized to higher-order tensors (as was the case in [Wang et al. 2020]).
limitations_and_societal_impact: While the limitations of the current work are clearly mentioned, no potential negative societal impacts are given. This is understandable, given the technical nature of the work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyzes gradient descent on the orthogonal tensor decomposition problem. More specifically, they consider a ground 4th order tensor with r orthonormal factors and an overparametrized estimate with m>r factors, and analyze the performance of (a variant of) gradient descent on the problem.

The paper establishes a close relationship between the dynamics of gradient descent and deflation based tensor decomposition. In deflation based tensor decomposition, the factors are recovered one at a time, and the factors recovered so far are subtracted from the original tensor to recover the next factor. The paper shows that the dynamics of a modified gradient descent algorithm are similar: the algorithm also recovers factors one at a time. 

The analysis uses the following key ideas, some of which are new and some are variants of previous techniques. First, the paper states a straightforward relation between gradient descent and the well-known tensor power method. This relation ensures that a non-negligible correlation with one of the original factors will get amplified on performing the gradient descent updates (similar to the tensor or matrix power methods which are well-analyzed). Next, the paper shows a local stability condition to ensure that once an iterate converges to one of the original factors, then it does not move away. This is done by adding a regularizer. Finally, the paper needs to do a periodic re-randomization of the iterates which have not converged so far to remove dependencies. To identify which factors have not converged so far, the paper establishes a relation between the norm of a factor and its correlation with any of the true factors. It appears that this is the most novel and important part of the proof. While periodic re-randomization has been introduced in the context of tensor power method and alternating least squares (ALS) and their variants, establishing a link between norm and correlation appears novel in this context.

The paper also does an empirical validation of the claims, but this is more to support the theory than a contribution in itself.
main_review: The paper appears to be mainly looking at the orthogonal tensor decomposition problem from the perspective of understanding neural networks and overparameterization. In this context, the main takeaway is that gradient descent recovers the true factors in the orthogonal case despite overparametrization. This is an interesting and novel contribution, though it would be more striking if there were more deeper takeways or implications. For instance, is it the case that that overparametrization is in fact necessary for recovering all the true factors? This is possible because one might imagine that multiple recovered factors could converge to the same original factors, and therefore if m=r then all the original factors will no longer be recovered. If true, such a result could complete the picture and highlight the role of overparametrization more.

While the paper is mainly focussing on the results in the context of deep learning theory, I think it would be useful to also put it in context of the known theory for tensor decomposition. Stronger guarantees than in the present paper (for example, extending to the non-orthogonal case) are known for the tensor power method, ALS, orthogonalized-ALS, simultaneous
diagonalization and higher order SVD etc., and it would be good to discuss at least some of the more relevant ones.

The paper is quite well-written. The algorithms and theoretical results are clearly described with ample intuition. The experiments also do a good job of explaining what is happening, particularly Fig. 1. 

Overall this appears to be a good paper, though I wouldn't argue strongly about it at this point.

----after author response-----

Thank you for your response, it would be nice to add some discussion for why overparametrization is necessary and some discussion of related work on tensor decomposition. I'll keep my score (7) and advocate for acceptance.
limitations_and_societal_impact: Other than the suggestions above, the authors adequately discuss the other limitations of the work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work studied a special training behavior of over-parametrized tensor decomposition by gradient-based methods. The paper pointed out this phenomena as the tensor deflation process and rigorously proved its convergence (Thm. 1) and the behaviors of factors (Prop. 1 and etc.) during the training. The implicit regularization by gradient method is an interesting and important issue in deep learning, and this work shows it would also happen in tensor decomposition. It may help the tensor researchers to develop more effective methods to seek for low-tensor-rank approximations, especially when the tensor model owns complex structures like tensor networks. However, unlike the closed work (li et al., 2020b) on matrices, several additional conditions and assumptions are imposed in the paper (norm regularization and re-initialization shown in Algo. 2), and the theoretical results seem to be only held for the decomposition task (the Fro. objective) and to be difficult for people to extend it into more general forms like tensor learning. It therefore limits the impact on the both tensor and machine learning community. 
main_review: Pros:

- The paper clearly discussed the tensor deflation process, which is interesting and somehow important.
- The proof thoughts and tricks like the *continuity argument* is instructive for me though I'm not mathematician.

Cons:

- It's difficult for me to evaluate if those mentioned modification is *mild* or not. If they are necessary for the both algorithm and theory. It will severely limit its application and extension on more sophisticated models in *machine learning*.
- Furthermore, there is also no discussion on if such implicit regularization on tensor decomposition outperforms the existing low-rank approximation methods or not, even though the  phenomena itself is indeed interesting.

### Comments

After reading the supp, I was convinced that the proof is a tough work and many tricks are impressive for me (engineering background). However, as a tensor researcher, I was always thinking about how *much new information or insight I can obtain from this impressive work?* For example, as the main contribution of the work, Thm. 3 only proves the convergence *if a symmetric orthogonal order-4 tensor is decomposed by Algo. 2,* which is closed to yet different from a trivial gradient method*.* It makes me consider why I need such a theorem, of which the form is very specific and the insight has been discussed by (li et al., 2020b).  As for Prop. 1 and other results, I partially understand they reflect the training behaviour of the factors, but I'm not sure if those results can fully support the claims given in the paper. For example, in line 238-239, the authors claim that the condition (c) shows a ground-truth component with large enough a_k can be always fitted. I think this claim is based on the upper-bound given at the end of line 233. Although in supp. there is discussion on lambda, I'm still confused if the bound is trivial (tight enough) or not and if or not it really can be used to support that those components can be always fitted. Therefore, it would be better to give more interpretation on each claim and more discussion to guide ML/AI researchers to exploit your results.

### Questions

1. What happens for your results if the tensor order equals two? In this case, what is the main difference from the work in (li et al., 2020b)? I have this question because the orth. assumption on factors makes the property of tensor decomposition be closed to its matrix counterpart. I therefore curious if your results can bring something new, which is significantly different from matrix.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper analyzes the dynamics of (a slightly modified) gradient flow for overparameterized symmetric CP tensor decomposition of order 4, where the minimized objective is the L2 distance from an orthogonally decomposable target tensor. The main technical result (Theorem 1) establishes that the modified gradient flow follows a trajectory similar to that of a tensor deflation process, in which components are learned one after the other, recovering the target tensor. Empirical evaluations corroborate the theoretical analysis.
main_review: I find the paper to be well written and technically sound (though I did not verify proofs in the appendix). In particular, the proof sketch for the main theorem is laid out in a manner that allows following the big picture, as well as specific details. Although the analyzed setting is rather restrictive --- symmetric order 4 decomposition, fully observed orthogonally decomposable target tensor, and a modified version of gradient flow --- the paper rigorously establishes greedy low rank learning under these conditions, similar to that described in Li et al. 2021 for matrices and Razin et al. 2021 for tensors. Furthermore, proofs of convergence for such non-convex problems are often highly non-trivial, even under simplifying assumptions. Overall, the contributions made improve upon current understanding of gradient-based dynamics for tensor factorizations.

There are a few drawbacks I see in this work besides the restricted setting (discussed below), yet I believe it is a worthy contribution and tend to recommend acceptance (given that these concerns are adequately addressed).

Drawbacks:
1. In Theorem 1, it seems that the approximation error cannot be arbitrarily small, but rather is bounded away from zero by a term dependent on the dimension. That is, for a certain fixed dimension it does not guarantee recovery of the ground truth to an arbitrary precision. Is this indeed the case? If so, I believe it is worth explicitly mentioning and clarifying. For example, in the introduction it is stated that recovery is to a desired accuracy.

2. In my opinion the works below are relevant, yet are not discussed in the related work section:
    - In addition to Li et al. 2021 which is referred to, Gidel et al. 2019, Gissin et al. 2020 , and Chou et al. 2020 also show a form of greedy low rank search for matrices, under certain conditions.
    - Razin & Cohen 2020 empirically demonstrates an implicit regularization towards low tensor rank for CP decompositions.


Additional (more minor) comments:
- In Equation (1), I believe the notation used for R over three inputs was not previously defined. Though one can extrapolate from the definition for two inputs, it might be worth explicitly defining.
- In Lemma 3 and Definition 2 the components are denoted by v instead of w as done up until that point.


Questions to authors:
1. Can the results be extended from order 4 tensors to arbitrary orders? If so, what is the dependence on the order, e.g. in the number of components necessary and the convergence rate?

2. In Theorem 1, what exactly is the condition on the error epsilon? It seems that it cannot be arbitrarily small, but rather bounded away from zero by a term dependent on the dimension.



References:

Li, Z., Luo, Y., and Lyu, K. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. International Conference on Learning Representations, 2021.

Razin, N., Maman, A., and Cohen N. Implicit regularization in tensor factorization. International Conference on Machine Learning, 2021.

Gidel, G., Bach, F., and Lacoste-Julien, S. Implicit regularization of discrete gradient dynamics in linear neural networks. In Advances in Neural Information Processing Systems, 2019.

Gissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning drives generalization. International Conference on Learning Representations, 2020.

Chou, H.-H., Gieshoff, C., Maly, J., and Rauhut, H. Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank. arXiv preprint arXiv:2011.13772, 2020.

Razin, N. and Cohen, N. Implicit regularization in deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems, 2020.


limitations_and_societal_impact: N/A --- This theoretical work does not have apparent negative societal impacts.
review_title: null

Meta-review: All the reviewers reached the consensus that the paper makes a valuable interesting contribution and should be accepted to the conference.  In the beginning of the discussion period, some concerns were raised about the practical utility of the results but after discussion among reviewers, the reviewers all agreed that the contribution is a nice technical addition to the growing literature on implicit regularization in factorization method.
Decision: Accept (Poster)