Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent

Thank you very much for taking the time to evaluate our paper and provide valuable feedback.

RIP Condition:

[Zhang et. al. 2021] shows that sub-Gaussian measurements $\mathcal{A}:\mathbb{R}^{n\times n\times k}\to\mathbb{R}^m$ have the RIP for tubal-rank $r$ tensors w.h.p. if $m\ge O(\delta^{-2}rnk)$. Since we desire $\delta=O(\kappa^{-4}r^{-1/2})$, we need $m\ge O(\kappa^{-8}r^2nk)$ measurements. For $k=1$, the matrix case, this is very much comparable to the results in [Li et al. 2018]. In our revision, we will add a discussion on the number of measurements necessary for the RIP to hold.

Role of Low Tubal Rank Condition in Implicit Regularization:

While Thm 3.1 holds for $R$ as small as $3r$, it is more interesting for $R\ge n$ so that our learner model, like [Li et. al. 2018], also does not explicitly encode low tubal rank structure, and no bound on the ground truth tubal rank is needed. In this case, we can substitute $\min\\{n,R\\}=n$ so there is no dependence on $R$.

When $R\ge n$ and the number of measurements satisfies $m<k(n^2+n)/2$ (but is still large enough for $\mathcal{A}$ to satisfy the RIP), there are infinitely many $\mathcal{U}\in\mathbb{R}^{n\times R\times k}$ with $\mathcal{A}(\mathcal{U}*\mathcal{U}^T) = \mathcal{A}(\mathcal{X} * \mathcal{X}^T)$, and thus, $\ell(\mathcal{U})=0$. However, the gradient descent iterates converge to a tensor of low tubal rank instead of one of the many high tubal rank tensors with zero loss. This suggests gradient descent is implicitly biased towards "simpler" tensors with low tubal rank.

We hope this clarifies the implicit bias phenomena, as well as the role of the low tubal rank condition. Also, we will add a remark after the main theorem discussing how for $R\ge n$ the theorem describes an implicit regularization phenomenon.

Motivation for our work and the use of tubal rank:

The study of implicit regularization was originally motivated by trying to understand how using gradient descent to train neural networks results in good generalization. However, implicit regularization has become its own field of study. Specifically, it has been proposed to design linear network architectures in such a way that an implicit bias towards a desired structure arises - as an alternative to explicit regularization. This viewpoint has been taken for the sparse recovery problem [Vaskevicius et. al. 2019] and the low-rank matrix completion problem [Li. et. al. 2018], but to the best of our knowledge, all previous works generalizing this approach to tensors either provide only a partial analysis or only analyze the gradient flow problem, not gradient descent, so we see our work as the first to establish this kind of approach for a tensor recovery problem. (In particular, we are not sure, which work about implicit bias of gradient descent for near-orthogonal tensor factorization you are referring to, so it would be great if you could provide a reference so that we can specifically comment.) In this context, we find the study of low tubal rank recovery interesting as this model has been shown to be useful in video representation.

We believe that this is an important line of research with many open questions. See our response to Reviewer phi4 for more details.

We agree other tensor ranks are also important, but we feel that our work is an important starting point for further analysis. This paper is not the end of the story, but rather one part of a larger line of research into implicit regularization for tensor recovery problems.

We agree that the additional motivational thread of using implicit regularization as an algorithm for structured recovery is currently not stressed enough in the paper. We will be sure to emphasize it in our revision.

Other:

Thank you for pointing out that tubal rank/t-SVD are not widely-used notions. We will expand the details we currently have in the Notations and Preliminaries section in the main body of our paper, as well as add a section on tubal rank/t-SVD in the Appendix.

Thank you for suggesting the question whether the tubal rank of the learner tensor gradually increases in the course of the gradient descent iterations. Indeed, during the spectral stage where the gradient descent iterates are small, gradient descent behaves approximately like a power method. As such, when the gradient descent iterates are expressed in the basis of the slices of the t-SVD of the tubal-symmetric tensor $\mathcal{I}+\mu(\mathcal{A}^*\mathcal{A})(\mathcal{X}*\mathcal{X}^T)$, the coefficients grow approximately exponentially at rates determined by the corresponding eigentubes. As such, it seems like one should be able to obtain similar results as in [2], however, we could not check the details carefully in the short revision period. We aim for a detailed investigation in future work.

See Response to Reviewer phi4 for the citations for [Vaskevicius et. al. 2019] and [Zhang et. al. 2019].

Thank you very much for your positive evaluation of our paper. We are glad you found it to be interesting and well-written.

Clarifying the Connection to Matrix Factorization:

Thank you for bringing the connection to matrix factorization to the discussion. Yes, while aiming to leverage matrix techniques as much as possible (no need to reinvent the wheel!), we encountered at lot of the technical complexities of these adaptations, which are briefly mentioned in Section 4.

To describe these technicalities in more details, we will extend Section 4. For example, the tubal-tensor iterates $\mathcal{U}\_t \in \mathbb{R}^{n \times R \times k}$ produced by gradient descent exhibit significant interactions between their slices when transitioning from step $t$ to $t+1$. This necessitated nontrivial estimations, such as those presented in Lemmas E.4 and E.5, to control these interactions and provide the respective bounds. Another intriguing point is that, one need to choose the learning rate $\mu$ and the initialization scale $\alpha$ very carefully for the noise term $\mathcal{U}\_{t} * \mathcal{W}\_{\perp, t}$ to grow slowly enough in each of the tensor slices in order to not allow overtaking the signal term $\mathcal{U}\_{t} * \mathcal{W}\_{t}$ in the norm.

Parameter Dependence in Theorem 3.1:

We agree that the parameter dependence in Theorem 3.1 looks unfamiliar at first sight. However, we find it not surprising that if the tensor is ill-conditioned, i.e., has a very small tubal singular value, gradient descent without regularization will have a hard time discovering that rank-one component unless the initialization is very small (in fact, our bound on the required number of iterations could also be expressed as a polynomial in the initialization parameter, making the exponential dependence implicit).

This is in line with prior results in the matrix sensing case, which also require an initialization of size depending exponentially on the condition number, see [Stöger and Soltanolkotabi 2021]. In the matrix case, however, this dependence is not as apparent, as the term with the exponential dependence is absorbed in one of the absolute constants, see the range for parameter $\beta$ in Lemma 8.6. of [Stöger and Soltanolkotabi 2021] with its proof and the corresponding results for tensors in our case. It is worth to mention that of course it is not clear in either case if the dependence needs to be exponential. We consider it an interesting question for follow-up work to investigate the precise dependence on the condition number.

Yes, some of the parameters appear polynomially in the bound, and as our numerical experiments, see Figure 4, show, indeed, the test error depends polynomially on the initialization parameter $\alpha$. It might be that the degree of the true polynomial dependence slightly differs from the one obtained theoretically; however, we strongly believe that the power $\frac{21}{16}$ approximates this dependence well.

Other:

Thank you for catching those typos. We will be sure to fix those in our revision.

Thank you very much for your positive evaluation of our paper and for recognizing our work as one of the few papers that fully analyzes gradient descent.

Motivation for our work and the use of tubal rank:

The study of implicit regularization was originally motivated by trying to understand how using gradient descent to train neural networks results in good generalization. However, implicit regularization has become its own field of study. Specifically, it has been proposed to design linear network architectures in such a way that an implicit bias towards a desired structure arises - as an alternative to explicit regularization. This viewpoint has been taken for the sparse recovery problem [Vaskevicius et. al. 2019] and the low-rank matrix completion problem [Li. et. al. 2018], but to the best of our knowledge, all previous works generalizing this approach to tensors either provide only a partial analysis or only analyze the gradient flow problem, not gradient descent, so we see our work as the first to establish this kind of approach for a tensor recovery problem. (In particular, we are not sure, which work about implicit bias of gradient descent for near-orthogonal tensor factorization you are referring to, so it would be great if you could provide a reference so that we can specifically comment.) In this context, we find the study of low tubal rank recovery interesting as this model has been shown to be useful in video representation.

We believe that it is an important line of research to answer questions like:

• What types of structured tensor recovery problems can be solved with implicit regularization?
• How to design the learner architecture to bias gradient descent towards solutions with the appropriate structure?
• Under what conditions and how quickly does convergence occur?
• Can one characterize the trajectory of the algorithm?

We do agree that other types of low rank tensor structures are also important, and we also agree that the corresponding analysis can be more challenging, but we feel that our work is an important starting point for further analysis. This paper is not the end of the story, but rather one part of a larger line of research into implicit regularization for tensor recovery problems.

We agree that the additional motivational thread of using implicit regularization as an algorithm for structured recovery is currently not stressed enough in the paper. We will be sure to emphasize it in our revision.

RIP Condition:

We would like to note that the RIP condition is a standard condition in the literature, and is used in similar works [Li et. al. 2018] and [Stöger and Soltanolkotabi 2021]. Essentially, this is necessary to ensure that there is one low tubal rank tensor for which the loss function is zero (although there are still infinitely many high tubal rank tensors for which the loss is also zero). Furthermore, [Zhang et. al. 2019] shows that a random sub-Gaussian measurement operator $\mathcal{A} : \mathbb{R}^{n \times n \times k} \to \mathbb{R}^m$ will satisfy the RIP for tubal-rank $r$ tensors with restricted isometry constant $\delta$ with high probability if $m \ge O(\delta^{-2}rnk)$. Since we desire $\delta = O(\kappa^{-4}r^{-1/2})$, we need $m \ge O(\kappa^{-8}r^2nk)$ measurements. Hence, many random measurement operators (with far fewer measurements than the number of entries in the tensor) will satisfy the RIP.

Other:

Thank you for bringing the papers [Ge and Ma 2017] and [Wang et. al. 2020] to our attention. We agree that they are related to our paper, and we will be happy to cite and include them in our paper's discussion.

Attempting to generalize our results to the M-rank setting (instead of tubal-rank) is an interesting idea for future work. In the case where the matrix $M$ is a scalar multiple of a unitary matrix, we believe that our results will generalize in a straightforward manner, although we have not checked all the details carefully. However, in the case where $M$ is not a scalar multiple of a unitary matrix, generalizing these results will be more difficult as our proof makes use of the fact that transforming a tensor into the Fourier domain (equivalently the $M$ domain) scales the Frobenius norm by a constant factor.

Thank you for pointing out the issue with lowercase/uppercase in our bibliography. We will be sure to fix this in our revision.

T. Vaskevicius, V. Kanade, and P. Rebeschini. "Implicit regularization for optimal sparse recovery." Advances in Neural Information Processing Systems. 2019.

F. Zhang, et al. "Tensor restricted isometry property analysis for a large class of random measurement ensembles." Science China. Information Sciences 64.1 (2021): 119101. https://arxiv.org/pdf/1906.01198