Understanding Deflation Process in Over-parametrized Tensor Decomposition
Authors: Rong Ge
Yunwei Ren
Xiang Wang
Mo Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: tensor decomposition
overparametrization
gradient flow
implicit regularization

Abstract: In this paper we study the training dynamics for gradient flow on over-parametrized tensor decomposition problems. Empirically, such training process often first fits larger components and then discovers smaller components, which is similar to a tensor deflation process that is commonly used in tensor decomposition algorithms. We prove that for orthogonally decomposable tensor, a slightly modified version of gradient flow would follow a tensor deflation process and recover all the tensor components. Our proof suggests that for orthogonal tensors, gradient flow dynamics works similarly as greedy low-rank learning in the matrix setting, which is a first step towards understanding the implicit regularization effect of over-parametrized models for low-rank tensors.

Understanding Deflation Process in Over-parametrized Tensor Decomposition
Rong Ge Duke University
Yunwei Ren"
Shanghai Jiao Tong University
ronggelcs duke. edu
201 2016renyunweiee jtu. edu. en
Xiang Wang"
Mo Zhou"
Duke University xwang@cs cs duke eddu
Duke University
mozhou@cs duke.
Abstract
In this paper we study the training dynamics for gradient flow wvrrpaaraeetried tensor decomposition problems. Empirically, such training process often first fits larger components and then discovers smaller components, which is similar to a tensor deflation process that is commonly used in tensor decomposition algorithms. We prove that for orthogonally decomposable tensor, slightly modified version gradient flow would follow a tensor deflation process and recover all the tensor components. Our proof suggests that for orthogonal tensors, gradient flow dynamics works similarly as greedy low-rank learning in matrix setting, which a first step towards understanding the implicit regularization effect of wver-parametrized models for low-rank tensors.
1 Introduction
Recently, pararaeetttriiioonnnn has been recognized as key feature of neural network optimization. line of works known as the Neural Tangent Kernel (NTK) showed that is possible to achieve zero training loss when the network is sufficiently over- over-parane perr-parmetrized (Jacot al., 2018; Du et al., 2018; Allen-Zhu et al., 2018b). However, the theory of NTK implics a particular dynamics called lazy training where the neurons do not many settings and can lead to worse generalization performance (Arora et al., 2019b). Many works explored other regimes of over-parameerization (Chizat and Bach, 2018: Mei et al., 2018) and analyzed dynamics beyond lazy training (Allen-Zhu et al., 20; Li et al., 2020a; Wang et al., 2020).
much (Chizat al., 2019), which is not natural in
pver-parametrizatioo does not only help neural network models. In this work, we focus on closely related problem of tensor (CP) decomposition. In this problem, we are given a tensor of the form
as (UI:)))
where a; 2 0 and U[; i] the i-th column of U E gdxr, The goal is to fit T using a tensor of similar form:
m
W 144
W[: 2
Alphhabetica order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0.5
1056
0.6
Residual c. drection
Besidual drection
0.4
Rosidual on drection
03
0.3
02
01
0.
0.0 200
200
600 800 1000
400 600
800
1000
steps
=steps
Figure 1: The training trajectory of gradient flow on orthogonal tensor decompositions. We chose T* Eg a with e E I2' and a:/ai+1 1.2. Our model T has 50 components and each component is randomly initialized with small norm 10-15 We ran the experiments from 5 different initialization and plotted the results separately. The left figure shows the loss 1 TT" and the right figure shows the residual on each e; direction that is defined as (T - (e
Here W is a d x m matrix whose columns are components for tensor T. The model is over- parametrized when the number of components m is larger than r. The choice of normalization factor of [/ a] 2] is made to accelerate gradient flow (similar to Li al. (2020a); Wang al. (2020)).
Suppose we run gradient flow on the standard objective 2 to the differential equation:
11 that is, we evolve W according
dW
dt - - (-111- -
can we expect T to fit T with good accuracy? Empirical results (see Figure 1) show that this is true for orthogonal tensor T long as is large enough. Further, the training dynamics exhibits behavior that is similar to a lensor deflation process: it finds the ground truth components one-by-one from larger component smaller component (if multiple ground truth components have similar norm they might be found simultaneously).
In this paper we show that with slight modification, gradient flow on over- over- over-parametrized tensor decomposition is guaranteed to follow this tensor deflation process, and can fit any orthogonal tensor to desired accuracy" (see Section 4 for the algorithm and Theorem I for the main theorem). This shows that for orthogonal tensors, the trajectory of modified gradient-flow is similar to a greedy low-rank process that was used to analyze the implicit bias of low-rank matrix factorization (Li et al., 2020b). We emphasize that our goal is not to propose another tensor decomposition algorithm. Instead, we hope our results can serve first step in understanding the implicit bias of wer-parameterized gradient descent for low-rank tensor problems.
1.1 Our approach and technique
To understand the tensor deflation process shown in Figure 1, intuitively we can think about the discovery and fitting of a ground truth component in two phases. Consider the beginning of the gradient flow compared to T In this case each component w in W will evolve according to a simpler dynamics that is similar to tensor power method, where updates w T @3 /)/ T (w _]] (see Section 3 for details).
example. Initially all the components in T are small, which makes T negligible
For orthogonal tensors, it's known that tensor power method with random initializations would be able to discover the largest ground truth components (see Anandkumar et al. (2014)). Once the largest ground truth component has been discovered, the corresponding component (or multiple components) w will quickly grow in norm, which eventually fits the ground truth component. The flat regions in the trajectory in Figure 1 correspond to the period of time where the components w' are small and
We say 1 is an orthogonal tensor if the ground truth components U iJ's orthonormal. *Due to some technical challenges, we actually require the target accuracy to be at least exp(-o(de log d)). This is only very mild restriction since the dependence is exponential in d, and in practice. d is usually large and this lower bound easily drop below the numerical precision.

---

T-T remains stable, while the decreasing regions correspond to the period of time where a ground truth component being fitted.
However, there are many challenges in analyzing this process. The main problem is that the gradient flow would introduce a lot of dependencies throughout the trajectory, making it harder to analyze the fitting of later ground truth components, especially ones that are much smaller. We modify the algorithm include reinitialization step per epoch, which alleviates the dependency issue. Even after the modification we still need a few more techniques:
Local stability One major problem in analyzing the dynamics in a later stage is that the components used to fit the previous ground truth components are still moving according to their gradients, therefore it might be possible for these components to move away. To address this problem, we add a small regularizer to the objective, and give new local stability analysis that bounds the distance to the fitted ground truth component both individually and on average. The idea of bounding the distance on average is important as just assuming each component w is close enough to the fitted ground truth component is not sufficient to prove that to cannot move far. While similar ideas were considered in Chizat (2021), the setting of tensor decomposition is different.
Norm/Correlation relation A key step in our analysis establishes relationship between norm and correlation: we show if component w crosses a certain norm threshold, then must have a very large correlation with one of the ground truth components. This offers an initial condition for local stability and makes sure the residual T - is almost close to an orthogonal tensor. Establishing this relation is difficult as unlike the high level intuition, even within a single epoch: is possible that one ground truth component is already fitted while no large component is near another ground truth component of same size. In previous work, Li et al. (2020a) deals with a similar problem for neural networks using gradient truncation that prevents components from growing in the first phase (and as a result has super-exponential dependency on the ratio between largest and smallest a.). We give a new technique to control the influence of ground truth components that are fitted within this epoch, so do not need the gradient truncation and can characterize the deflation process.
cannot guarantee T - T remains unchanged
1.2 Related works
Neural Tangent Kernel There is a recent line of work showing the connection between Neural Tangent Kernel (NTK) and sufficiently wide neural networks trained by gradient descent (Jacot et al., 2018; Allen-Zhu et al., 2018b; Du et al., 2018, 2019; Li and Liang, 2018; Arora et al., 2019b,c; Zou et al., 2020: Oymak and Soltanolkotabi, 2020; Ghorbani et al., 2021). These papers show when the width of a neural network is large enough, it will stay around the initialization and its training dynamic is close to the dynamic of the kernel regression with NTK. In this paper go beyond the NTK setting and analyze the trajectory from a very small initialization.
Mean-field analysis There another line of works that use mean-field approach to study the optimization for infinite-wide neural networks (Mei et al., 2018; Chizat and Bach, 2018; Nguyen and Pham, 2020; Nitanda and Suzuki, 2017: Wei et al., 2019; Rotskoff and Vanden- Fijnden,, 2018; Sirignano and Spiliopoulos, 2020). Chizat et al. (2019) showed that, unlike NTK regime, the parameters can move away from its initialization in mean-field regime. However, most of the existing works need width to be exponential in dimension and do not provide polynomial convergence rate.
Beyond NTK There are many works showing the gap between neural networks and NTK (Allen- Zhu and Li. 2019; Allen-Zhu et al., 3018a; Ychudai and Shamir, 2019; Ghorbani al., 2019, 2020; Dyer and Gur-Ari, 2019; Woodworth et al., 2020; Bai and Lee, 2019; Bai et al., 2020; Huang and Yau,
2020; Chen et al., 2020). In particular, Li et al. (2020a) and Wang et al. (2020) are closely related with our setting. While Li et al. (2020a) focused on learning two-layer ReL.U neural networks with orthogonal weights, they relied on the connection between tensor decomposition and neural networks (Ge et al., 2017) and essentially worked with tensor decomposition problems. In their result, all the as's are within a constant factor and all components are learned simultaneously. We allow ground truth components with very different scale and show a deflation phenomenon. Wang et al. (2020) studied learning a low-rank not-orthogonal tensor, but they only showed the learned tensor T will eventually be close to the ground truth tensor 7 and does not guarantee the components of T will
3

---

align with the components of T On the other hand, we fully characterize the training trajectory and the components of the learned tensor.
Implicit regularization Many works recently showed that different optimization methods tend to converge to different optima and have different optimization trajectories several settings (Saxe et al., 2014; Soudry et al., 2018; Nacson et al., 2019; Ji and Telgarsky, 2018a,b, 2019, 2020; Gunasekar et al., 201 b Moroshko et al., 2020; Arora et al., 2019a; Lyu and Li, 2019; Chizat and Bach, 2020). In partieular, Saxe al. (2014) 4) related the dynamics of gradient descent the magnitude of the singular values of the target weight matrices for linear networks with orthogonal inputs. The phenomenon there is qualitatively similar very different. The more related and recent works are Li et al. (2020b) and Razin et al. (2021). Li al. (2020b) studied matrix factorization problem and showed gradient descent with infinitesimal initialization is similar to greedy low-rank learning, which is a multi-epoch algorithm that finds the best approximation within the rank constraint and relax the constraint after every epoch. Razin et al. (2021) studied the tensor factorization problem and showed that it biases towards low rank tensor. Both of these works considered partially observable matrix or tensor and are only able to fully analyze the first epoch (i.e., recover the largest direction). We focus on simpler setting with obbly-lbe ground truth tensor and give complete analysis of learning all the ground truth components.
results, but the settings and the proof techniques
1.3 Outline
In Section 2 introduce the basic notations and problem setup. In Section 3 review tensor deflation process and tensor power method. We then give our algorithm in Section 4. Section 5 gives the formal main theorem and discusses high-level proof ideas. We conclude in Section 6 and discuss some limitations of the work. The detailed proofs and additional experiments are left in the appendix.
2 Preliminaries
Notations We use upper-case letters to denote matrices and tensors, and lower-case letters to denote vectors. For any positive integer n, use [n] to denote the set 21, n). We use I denote d x d identity matrix, and omit the subscript d when the dimension is clear. We & Unif(( ') to denote the uniform distribution over (d didienssio sphere with radius 50.
For vector e, we use ||a|| to denote its fa norm. We use Ug to denote the k-th entry of vector and use V-a to denote vector with its k-th entry removed. We use to denote the normalized vector T w/ ||]]] and use ūn to denote the k-th entry of 0.
For matrix A, use AlE, i] to denote its i-th column and col(A) denote the set of all column vectors of A. For matrix M or tensor T' we use || and ||T']] to denote their Frobenius norm, which is equal to the & norm of their vectorization.
For simplicity we restrict our attention to symmetric 4-th order tensors. For a vector v E Rd we use y0 to denote d x d x d x d tensor whose (i,j,k, k, 1)-th entry is equal to 1i Suppose Eu 8 we define T()844) as Σn to (w. b)² T( I) as En (w, v) w, and 0 u, En (w. u)² (w, u) w.
For clarity, always call component in T ground truth component and call a component in our model simply as component.
Problem setup We consider the problem of fitting 4-th order tensor. The components of the ground truth tensor is arranged as columns of matrix U E ddd and the tensor I is defined as
T = Σ a (U
where 01 2 02 a; 2 /d for all e [r]. This is without loss of generality because the target accuracy is and we can safely ignore very small ground truth components with a; < </vd.. In this paper, we focus on the case where the components are orthogonal that is, the columns U[: [,, il's are orthonormal. For
ar 2 0 and Σ
1. For convenience in the analysis, assume

---

simplicity we assume without loss of generality that U[ = where is the i-th standard basis vector". To reduce the number of parameters we also assume r d, again this without loss of generality because we can simply set a; = O for i i>ri>
There can be many different ways parametrize the tensor that works (Wang et al., 2020; Li et al., 2020a), we use an over- over-vvvannnn peee-paaamttrized and two-homogeneous tensor
fit 7 Following previous
m
T
Here W E Rd is a matrix with m columns that corresponds to the components in T. It is overparametrized when m r.
Since the tensor only depends on the set of columns W|: il instead of the orderings of the columns, for the most part of the paper will instead write the tensor T as
w
T
Σ
(W) ||0||2
where col(W) is the of all the column vectors in W. This allows to discuss the dynamics of coordinates for component to without using the index for the component. In particular, w; always represents the i-th coordinate of the vector w. This representation is similar to the mean-field setup (Chizat and Bach, 2018; Mei et al., 2018) where one considers a distribution on w. however since we do not rely on analysis related infinite-win width limit we use the sum formulation instead. For the case of presentation, we choose to restrict our setting to fourth-order tensor decomposition, but our results can be easily generalized to tensor with order at least three.
Tensor deflation process and tensor power method
In this section we will first discuss the basic tensor deflation process for orthogonal tensor decompo- sition. Then we show the connection between the tensor power method and gradient flow.
Tensor deflation For orthogonal tensor decomposition, a popular approach is to first fit the largest ground truth component in the tensor, then subtract it out and recurse on the residual. The general process given in Algorithm approximation. For example, Anandkumar et al. (2014) uses tensor power method, which picks many random vectors w, and update them as w T @w /)/ I (w ,I]l-
this process, there are multiple ways to find the best rank-
Algorithm Tensor Deflation Process
Input: Tensor 7
Output: Components W such that T Ewecok(w) w / Initially let the residual R be T
while |R]| F is large do Find the best rank approximation @ ||| for R. Add new column in W, and let R R @4 /||w||2
end while
Tensor power method and gradient flow If we run tensor power method using tensor T* that is equal to Dd =mm a then component will converge to the direction of e, where is equal to arg max; o,W If there is tie (which happens with probability 0 for random w), then the point will be stuck at a saddle point.
Let's consider running gradient flow on with objective function || 1 1 as T E Ewecol(W) 0/ / T does not change much the residual = T T is close to
"This is without loss of generality because gradient flow (and our modifications) is invariant under rotation of the ground truth parameters.
5

---

In this case the trajectory of one component w is determined by the following differential equation:
constant.
dw 4R (w, T) - 2R( 10 S
(1)
dt
To understand how this process works, we can take a look at du the growth rate for w³). If R = T then we have:
(intuitively this corresponds to "
duž /tt w
8a. - Σ a jE(d
From this formula it is clear that the coordinate with larger a, has a faster growth rate, so eventually the process will converge to e, where is equal to arg max; a,wy same the tensor power method. Because of their similarity later we refer to dynamics in Eqn. (1) as tensor power dynamics.
4 Our algorithm
Our algorithm is modified version of gradient flow described in Algorithm 2. First, we change the loss function to
1 L(W) = 2 11T - TT" + |
The additional small regularization ||] allows to prove local stability result that shows if there are components w that are close to the ground truth components in direction, then they will not move too much (see Section 5.1).
Our algorithm runs multiple epochs with increasing length. We use W(+.)) to denote the weight matrix in epoch s at time L. We similar notation for tensor T(s.), In each epoch we try fit ground truth components with 2 8(*), In general, the time it takes to fit one ground truth direction inversely proportional to its magnitude a, The earlier epochs have shorter length so only large directions can be fitted, and later epochs are longer to fit small directions.
At the middle of each epoch, we reinitialize all components that do not have large norm. This serves several purposes: first we will show that all components that exceed the norm threshold will have good correlation with one the ground truth components, therefore giving an initial condition to the local stability result; second, the reinitialization will reduce the dependencies between different epochs and allow us to analyze each epoch almost independently. These modifications do not change the dynamics significantly, however they allow us to do rigorous analysis.
Algorithm 2 Modified Gradient Flow
Input: Number of components m, initialization scale ög, re-initialization threshold on increasing rate of epoch length target accuracy e, regularization coefficient À
Output: Tensor T' satisfying I|T' 1 S
Initialize (0,00) as a x m matrix with each column (0.0)) i.i.d. sampled from on Unif((dd)))
((0) + 00000) - | p: + +0
while ( | > do
d Phase 1: Starting from W(++0), run gradient flow for time t\() = O geon log(d) )-
Reinitialize all components that have f2 norm less than òn by sampling i.i.d. from do Unir(
Phase 2: Starting from W(sa()), gradient flow for t +{*) O O log((1/6) (oog///A) time
39)
W(++1.0) +- W(edd)) g(0+1) <- (1) - 7); - $ end while

---

Main theorem and proof sketch
In this section we discuss the ideas to prove the following main theorem
Theorem For any E 2 exp(-o(d/ log d)), there exists 7 ( m = poly(d), A min[OOlog d/d), ()) a (ii///) ((?2), ((2/d)), 51 = O(a2/2 /m)//))
50 = / log (d)) such that with probability - 1/poly(d) in the (re)-inittalizzaiinn, Al- gorithm 2 terminates (log(d//)) epochs and returns a tensor T such that
I p
Intuitively, epoch of Algorithm 2 will try to discover all ground truth components with a, that is least large g(+), The algorithm does this in two phases. In Phase the small components will evolve according to tensor power dynamics. For each ground truth component with large enough a, that has not been fitted yet, we hope there will be at least one component in W that becomes large and correlated with e;. We call such ground truth components "discovered". Phase ends with a check that reinitilizes all components with small norm. Phase 2 is relatively short, and in Phase 2 guarantee that every ground truth component that has been discovered become "fitted", which means the residual T T becomes small in this direction.
However, there are still many difficulties in analyzing each of the steps. In particular, why would ground truth components that are fitted in previous epochs remain fitted? How to guarantee only components that are correlated with a ground truth component grow to a large norm? Why wouldn't the gradient flow in Phase 2 mess up with the initialization we require in Phase 1? We discuss the high level ideas to solve these issues. In particular, in Section 5,1 we first give an induction hypothesis that is preserved throughout the algorithm, which guarantees that every ground truth component that fitted remains fitted. In Section 5.2 we discuss the properties in Phase 1, and in Section 5.3 we discuss the properties in Phase 2.
5.1 Induction hypothesis and local stability
In order to formally define what it means for ground truth component to be "discovered" or "fitted", we need some more definitions and notations.
Definition 1. Define s(*.1) S [m]] as the subset of components that satisfy the following conditions: the k-th component is in s(0.0) if and only if there exists some time (s', .t) that is no later than (s, t) and no earlier than the latest re-initialization of W [E, ki] such that
Wid (F 81 and [W(s.)[ 11,12111111
We say that ground truth component is discovered in epoch time I, if S( not empty.
Intuitively, 5(0.0) is a subset of components in W such that they have large enough norm and good correlation with the i-th ground truth component. Although such components may not have large enough norm to fit a, yet, their norm will eventually grow. Therefore we say ground truth component i discovered when such components exist.
For convenience, we shorthand (=()))) e [:, E s(0.1) by wlls.) E 5(0.0) Now we will discuss when a ground truth component fitted, for that, let
Σ 1
Here a((".t) is the total squared norm for all the components in s(a.t), We say ground truth component is fitted if a; 1-- a( (8.1)
< 2X.
'In the theorem statement, we have a parameter a that not used in our algorithm but is very useful in the analysis (see for example Definition 1). Basically, a measures the closeness between component and its corresponding ground truth direction (see more in Section 5.1).
7

---

Note that one can partition the columns in W using sets S((.t), giving d groups and one extra group that contains everything else. We define the extra group as s(s.t) := [m] \ Ukeja s(x.t)
For each of the non-empty s(*:() we can take the average of its component (weighted by ||
E/ f(w((tt))=
Σ
/ f(wllat))
(r,t)
aj
If sf.:0) = 23, we define B/( f(w((..)) zero. Now we are ready to state the induction hypothesis:
Proposition 1 (Induction hypothesis). In the setting of Theorem 1, for any epoch s and time and every k E [d], the following hold.
(a) For any wloot) E s(ait), we have
2
Wi
2 -a a.
(b) If Sf is nonempty,
B(a.)) k,w k
2 21- 1-a22445mm -4sm67.
(c) We always have ag 1---a 0z ((at))
(8.t) smo7: if 2 i- werther know as -a(()) S X smof.
(d) If (flss)) E s(a.t) then |1(5)00|| S 61.
We choose of small enough so that smoe is negligible compared with a2 and X. Note that Proposition 1 is maintained throughout the algorithm, all the large components will be fitted, which directly implies Theorem 1. Detailed proof is deferred Appendix
Condition (c) shows that for a ground truth component & with large enough dg. it will always be fitted after the corresponding epoch (recall from Theorem 1 that x = (s)/vd)). Condition (d) shows that components that did not discover any ground truth components will always have small norm (hence negligible in most parts of the analysis). Conditions (a)(b) show that as long as ground truth component i has been discovered, all components that are in s( will have good correlation, while the average of all such components will have even better correlation. The separation between individual correlation and average correlation is important in the proof. With only individual bound, we cannot maintain the correlation no matter how small a is. Here is an example below:
Claim 2. Suppose T Ex and T = / / w0 [| with ||w||] ||al| [2/3, 1].
Suppose t2 = 1 a and Uj = Wk U-k = - - Assuming ||=l| < c1 and a S o2 for small enough
constants C1, C22 we have d
de 0h < 0.
In the above example, both 0 and are close to ex but they are opposite in other directions (8-k w- The norm of e is very small compared with that of w. Intuitively, we can increase u- so that more aligned with ex. See the rigorous analysis Appendix A.6.
the average of e and
The induction hypothesis will be carefully maintained throughout the analysis. The following lemma guarantees that in the gradient flow steps the individual and average correlation will be maintained.
Lemma 3. In the setting of Theorem 1, suppose Proposition I holds in epoch s time I, we have
d
(1,))
ak -a al.10) (1 [10 (2(20)1p)))))))))))))) 0 (a)
dt
(e.)) di [u
12:0)
> ak -a (0.00) (1
10 (o.)))
k, (o) (200011)) -O(a²).
In particular, when as (e.t) [n (ele.00p when (e [m) (2
> s())) = ((v((a)))))) we have de [1m0 when (1p(::0pp a o²
and d (
di
The detailed proof for the local stability result can be found in Appendix A. Of course, fully prove the induction hypothesis one needs to talk about what happens when a component enters ((..t) and what happens at the reinitialization steps. We discuss these details in later subsections.
8

---

5.2 Analysis of Phase 1
In Phase our main goal is to discover all the components that are large enough. We also need to maintain Proposition 1. Formally we prove the following:
Lemma (Main Lemma for Phase 1). In the setting of Theorem I, suppose Proposition holds at
(s, 0). For e = {0)) + + + + with t(") (dd/ (B(s) log d)), th {())" (dd/(3()) log d)),
(s)er @(log(d/a)/88) with probability
1/poly(d) we have
1. Proposition holds at (s, for any 0 st < t (1) and also for fort= 194) after reinitialization.
2. If ak 2 3(0) and S( = Ø, we have S
(8.11%) s( + Ø and dg
2 89.
3. If s 2 and s((.11)) + Ø, we have ok 2 ( for universal constant 0 < C
Property 2 shows that large enough ground truth components are always discovered, while Property 3 guarantees that no small ground truth components can be discovered. Our proof relies on initial components being "lucky" and having higher than usual correlation with one of the large ground truth components. To make this clear we separate components into different sets (here we use v to denote component in W):
Definition 2 (Partition of (re-)initialized components). For each direction E [d], define the set of good components $ and the set of potential components
g(a) Sippot as follow, where (())
1 1/( if s( Ø, and r( 1/(8>t("") otherwise. Here Pi (s) enough absolute constant.
== ccTT and cp is small
s(e)
igoood == {k| [0 12 2 (0) + p
-1(() - -p3-) .Vj ,vj+ and (s.0)) = w.s..0) | k]}
s(a) ppot == {Kl 10 12 2 (s))_ pi (z) and vl000) w(.00) k.
Let s(())
good = (()))
i.good and s(*)
= U,S(:) iop
We also define the set of bad components s(s)
pot
s(e)
= (k 3i e s.t. [0| (0 2 p((o) pi
(e)
[1(000012 1 22 - o3 and (=.00) W((.0) [;,k]]] k}}.
For convenience, we shorthand ((s..) E [w(* [: E Ss.good) by v(*a) E Ss.good (same for So and Stoa). Intuitively, the good components will grow very quickly and eventually pass the norm threshold. Since both good and potential components only have one large coordinate, they will become correlated with that ground truth component when their norm is large. The bad components are correlated with two ground truth components so they can potentially have a large norm while not having very good correlation with either one of them. In the proof we will guarantee with probability at least 1 - 1 1/poly (d) that good components exists for all large enough ground truth components and there are bad components. The following lemma characterizes the trajectories of different type of components:
Lemma 5. In the setting of Lemma 4, for every i E [d]
1. (Only good/potential components can become large) If ((ss)) & spot || = ((6) and [o] ( = (log(d)/d (d) for all i E [d] and I. < (())
2. (Good components discover ground truth components) If g(s)
igood $ D. there exists ((.e(())
such that |uledft)) |||
82 and s(ead)) 4
3. aLgg components are correlated with ground truth components) If [|060.00] 2 8n for some E (10) there exists E [d] such that p(a.t) s!a..)
The proof of Lemma 5 is difficult as one cannot guarantee that all the ground truth components that are hoping fit in the epoch will be fitted simultaneously. However are able show that T-7" remains near-orthogonal and control the effect of changing T T within this epoch. The details are in Appendix B.

---

5.3 Analysis of Phase 2
In Phase 2 we will show that every ground truth component that's discovered in Phase will become fitted, and the reinitialized components will preserve the desired initialization conditions.
Lemma 6 (Main Lemma for Phase 2). In the setting of Theorem 1, suppose Proposition holds at (s, ()))
have for (6) -t(-) 0 (llg((1//)))) (logg//))) (log(1/A))
),
g(o)
1. Proposition holds at (s, for any ( St 1/
2. If sla # Ø0 we have 0g - 0x < 2X.
(8.12
3. For any component v that was reinitialized at th"), we have |olass = =0(6)) and (0.06))) ] 02
(o(o))) for every i [d].
The main idea is that as long direction has been discovered, the norm of the corresponding components will increase very fast. The rate of that characterized by the following lemma. Lemma (informal). In the setting of Theorem 6, for any {1-) St (
d (e,))
2 (2(ax a!.:0) - 0
0x a(2.0)
dt
In particular, after O ( time, we have ak.:
(s.1) 0x S
By the choice of & and X, the length Phase 2 is much smaller than the amount of time needed for the reinitialized components to move far, allowing us prove the third property in Lemma 6. Detailed analysis is deferred to Appendix C.
6 Conclusion
In this paper we analyzed the dynamics of gradient flow for over-parametrized orthogonal tensor decomposition. With very mild modification to the algorithm (a small regularizer and some initializations). we showed that the trajectory is similar to tensor deflation process and the greedy low-rank procedure in Li et al. (2020b). These modifications allowed us prove strong guarantees for orthogonal tensors of any rank, while not changing the empirical behavior of the algorithm. We believe such techniques would be useful in later analysis for the implicit bias of tensor problems.
major limitation of our work that it only applies to orthogonal tensors. Going beyond this would require significantly new ideas-we observed that for general tensors, overparametrized gradient flow may have very different behavior compared to the greedy low-rank procedure, as is possible for two large component in the same direction to split into two different directions (see more details in Appendix E). We leave that as an interesting open problem.
Acknowledgements
Rong Ge, Xiang Wang and Mo Zhou are supported part by NSF Award CCF- CCF- 1845171 (CAREER), CCF-1934964 (Tripods), Sloan Research Fellowship, and a Google Faculty Research Award.
References
Allen-Zhu. Z. and Li, Y. (2019). What can resnet learn efficiently, going beyond kernels? arXiv
preprint arXiv: 3005:/995..033
Allen-Zhu, Z.,, Li, Y., and Liang, (2018a). Learning and generalization overparameterized neural networks, going beyond two layers. arXiv preprint
10

---

Allen-Zhu, Z., Li, Y., and Song. Z. (2018b). A convergence theory for deep learning via over parameterization. arXiv preprint wrXiv:1811.03962
Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., and Telgarsky, M. (2014). Tensor decompositions for learning latent variable models. Journal of machine learning research, 15:2773-2832.
Arora, S., Cohen, N., Hu, W., and Luo, Y. (2019a). arXiv preprint arXiv: 1905.19655.
in deep matrix factorization.
Arora, S., Du, S. S., Hu, W. Li, Z.,, Salakhutdinov, R., and Wang, R. (2019b). On exact computation with an infinitely wide neural net. arXiv preprint
Arora, S., Du, S. S., Hu, W., Li, 7., and Wang. R. (2019c). Fine-grained analysis of optimization and generalization for overparameterizee two-layer neural networks. arXiv preprint arXiv: 085584.
Bai, Y., Krause, B., Wang, H., Xiong. C.. and Socher, R. (2020). Taylorized training: Towards better approximation of neural network training at finite width. arXiv preprint arXiv:2002.04010.
Bai, Y. and Lee, D. (2019). Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint
Chen, M., Bai, Y., Lee, J. D., Zhao, T., Wang, H., Xiong, C., and Socher, R. (2020). Towards under- standing hierarchical learning: Benefits of neural representations. arXiv preprint arXiv:2006.1344
Chizat, L. (2021). Sparse optimization measures with over-parameterized gradient descent. Mathematical Programming, pages 1-46.
Chizat, L. and Bach, F. (2018). On the global convergence of gradient descent for over- pa---aattttrrzedd models using optimal transport. Advances in neural information processing systems, pages 3036-3046.
Chizat, L. and Bach, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1308-1338. PMLR.
Chizat, L.,, Oyallon, E., and Bach, F. (2019). On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pages 2933-2943.
Du, S., Lee, J., Li, H., Wang. I.., and Zhai, X. (2019). Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pages 1675-1685. PMLR.
Du, S., Zhai, X., Poczos, B., and Singh, (2018). Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.02054.
Dyer, E. and Gur-Ari, G. (2019). Asymptotics of wide networks from feynman diagrams, arXiv preprint 1:XVv:1909.11000
Ge, R., Lee, J. D., and Ma, T. (2017). Learning mee-iddeen- layer neural networks with landscape design. arXiv preprint 1rX1v:1711.00501.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2019). Limitations of lazy training of two-layers neural network. In NeurIPS.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2020). When do neural networks outperform kernel methods? arXiv preprint arXiv:2006. 13409.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2021). Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. (2018a). Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR.
Gunasekar, S., Lee, J., Soudry, D., and Srebro, (2018h). Implicit bias of gradient descent on linear convolutional networks. arXiv preprint

---

Huang, J. and Yau, H.-T. (2020). Dynamics of deep neural networks and neural tangent hierarchy. In International Conference on Machine Learning, pages 4542-4551. PMLR.
Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization
in neural networks. In Advances neural information processing systems, pages 8571-8580.
Ji, Z. and Telgarsky. M. (2). Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02000
Ji, Z. and Telgarsky. M. (2018b). Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300
Ji, Z. and Telgarsky, M. (2019). A refined primal-dual analysis of the implicit bias. arXiv preprint arXiv: arXiv:1906.04500
Ji, Z. and Telgarsky, M. (2020). Directional convergence and alignment deep learning. arXiv preprint 2.Xiv:20006066557
Lakshmikantham, V., Bainov, D., and Simeonov, S. (1989). Theory of impulsive differential equations. World Scientific.
Li, and Liang Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pages 8157- 8166.
Li Y., Ma, T., and Zhang, H. R. (2020a). Learning over-parametrized two-layer neural networks beyond ntk. In Conference Learning Theory, pages 2613-2682. PMLR.
Li, Z., Luo, Y., and Lyu, K. (2020b). Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839
Lyu, K. and Li, J. (2019). Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 1906.05896.
Mei, S., Montanari, A., and Nguyen, P.-M. (2018). A mean field view the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33))77665-77777
Moroshko, E., Gunasekar, S., Woodworth, B., Lee, J. D., Srebro, N., and Soudry, (2020). Implicit bias in deep linear classification: Initialization scale vs training accuracy. arXiv preprint arXiv:2007.06733.
Nacson, M. S., Lee, J., Gunasekar, S., Savarese, P. H. P., Srebro, N., and Soudry, D. (2019). Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR.
Nguyen, P.M. and Pham, H. (2020). A rigorous framework for the mean field limit of multilayer neural networks. arXiv preprint 1.Xiv:200//1144:
Nitanda, and Suzuki, T. (2017). Stochastic particle gradient descent for infinite ensembles. arXiv preprint arXiv:1712.05433,
Oymak, S. and Soltanolkotabi, M. (2020). Towards moderate overparameterization: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory.
Razin, N., Maman, A., and Cohen, N. (2021). Implicit regularization in tensor factorization. arXiv preprint arXiv:2 102.09972.
Rotskoff, G. M. and Vanden- Mijjee-E,jnden, E. (2018). Trainability and accuracy neural networks: An interacting particle system approach. arXiv preprint 100500.....
Saxe, A. M., Mcclelland, J. I.., and Ganguli, S. (2014). Exact solutions to the nonlinear dynamies of learning in deep linear neural network. In In International Conference Learning Representations.
12

---

Sirigmano, J. and Spiliopoulos, K. (2020). Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications. 13063):1200-1852
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. (2018). The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1):2822-2878.
Tao, T. (2006). Nonlinear dispersive equations: local and global analysis. American Mathematical Society.
Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
Wang, X., Wu, C., Lee, D., Ma, and Ge, R. (2020). Beyond lazy training for over over- wer-parameterized tensor decomposition. arXiv preprint arXiv:2010.1135.
Wei, C., Lee, J. D., Liu, Q. and Ma, T. (2019). Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, pages 9712-9724.
Woodworth, B., Gunasekar, S., Lee, J. D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. (2020). Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673. PMLR.
Ychudai, G. and Shamir, O. (2019). On the power and limitations of random features for understanding neural networks. arXiv preprint
Zou, D., Cao, Y., Zhou, D., and Gu, Q. (2020). Gradient descent optimizes ever-parameterized deep relu networks. Machine Learning, 109(3):467-492.
13


Reviews:
[{"review_id": "Q_PS7-70rfo", "reviewer": "Reviewer_tiKB", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n- The paper clearly discussed the tensor deflation process, which is interesting and somehow important.\n- The proof thoughts and tricks like the *continuity argument* is instructive for me though I'm not mathematician.\n\nCons:\n\n- 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*.\n- 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.\n\n### Comments\n\nAfter 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.\n\n### Questions\n\n1. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-10"}, "extra_text": {}}, {"review_id": "LIgLG950onG", "reviewer": "Reviewer_b9Va", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The 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.\n\nThat 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. \n\nSecondly, 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.\n\nFinally, 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]).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "C05z6o5lAOC", "reviewer": "Reviewer_2dDS", "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.\n\nThe 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. \n\nThe 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.\n\nThe paper also does an empirical validation of the claims, but this is more to support the theory than a contribution in itself.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The 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.\n\nWhile 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\ndiagonalization and higher order SVD etc., and it would be good to discuss at least some of the more relevant ones.\n\nThe 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. \n\nOverall this appears to be a good paper, though I wouldn't argue strongly about it at this point.\n\n----after author response-----\n\nThank 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Other than the suggestions above, the authors adequately discuss the other limitations of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "5ZHXXcXAhM", "reviewer": "Reviewer_ubkb", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nThere 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).\n\nDrawbacks:\n1. 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.\n\n2. In my opinion the works below are relevant, yet are not discussed in the related work section:\n    - 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.\n    - Razin & Cohen 2020 empirically demonstrates an implicit regularization towards low tensor rank for CP decompositions.\n\n\nAdditional (more minor) comments:\n- 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.\n- In Lemma 3 and Definition 2 the components are denoted by v instead of w as done up until that point.\n\n\nQuestions to authors:\n1. 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?\n\n2. 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.\n\n\n\nReferences:\n\nLi, 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.\n\nRazin, N., Maman, A., and Cohen N. Implicit regularization in tensor factorization. International Conference on Machine Learning, 2021.\n\nGidel, 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.\n\nGissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning drives generalization. International Conference on Learning Representations, 2020.\n\nChou, 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.\n\nRazin, N. and Cohen, N. Implicit regularization in deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems, 2020.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A --- This theoretical work does not have apparent negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)