A unifying view on implicit bias in training linear neural networks
Authors: Chulhee Yun
Shankar Krishnan
Hossein Mobahi
Venue: ICLR 2021 Poster (2021)
Keywords: implicit bias
implicit regularization
convergence
gradient flow
gradient descent

Abstract: We study the implicit bias of gradient flow (i.e., gradient descent with infinitesimal step size) on linear neural network training. We propose a tensor formulation of neural networks that includes fully-connected, diagonal, and convolutional networks as special cases, and investigate the linear version of the formulation called linear tensor networks. With this formulation, we can characterize the convergence direction of the network parameters as singular vectors of a tensor defined by the network. For $L$-layer linear tensor networks that are orthogonally decomposable, we show that gradient flow on separable classification finds a stationary point of the $\ell_{2/L}$ max-margin problem in a "transformed" input space defined by the network. For underdetermined regression, we prove that gradient flow finds a global minimum which minimizes a norm-like function that interpolates between weighted $\ell_1$ and $\ell_2$ norms in the transformed input space. Our theorems subsume existing results in the literature while removing standard convergence assumptions. We also provide experiments that corroborate our analysis.

Published as a conference paper at ICLR 2021
A UNIFYING VIEW ON IMPLICIT BIAS IN TRAINING LINEAR NEURAL NETWORKS
Chulhee Yun'
Shankar Krishnan
Hossein Mobahi Google Research hmobah i @ww.gggle.oo.ooo... com
MIT
Google Research
chu Shulheey@miit.eem
skri goon le com
ABSTRACT
We study the implicit bias gradient flow (i.e., gradient descent with infinitesi- mal step size) on linear neural network training. We propose tensor formulation of neural networks that includes fully-connected, diagonal, and convolutional net- works as special cases, and investigate the linear version of the formulation called linear tensor networks. With this formulation, we can characterize the conver- gence direction of the network parameters as singular vectors of a tensor defined by the network. For L-layer linear tensor networks that are orthogonally decom- posable, we show that gradient flow on separable classification finds stationary point of the f max-margin problem in a "transformed" input space defined by the network. For underdetermined regression, we prove that gradient flow finds a global minimum which minimizes a norm-like function that interpolates between weighted E, and & norms the transformed input space, Our theorems subsume existing results in the literature while removing standard convergence assump- tions. We also provide experiments that corroborate our analysis.
INTRODUCTION
Overparametrized neural networks have infinitely many solutions that achieve zero training error, and such global minima have different generalization performance. Moreover, training neural network is a high-dimensional nonconvex problem, which is typically intractable to solve. However, the success of deep learning indicates that first-order methods such gradient descent stochastic gradient descent (GD/SGD) not only (a) succeed in finding global minima, but also (b) are biased towards solutions that generalize well, which largely has remained mystery in the literature.
To explain part (a) of the phenomenon, there is a growing literature studying the convergence of GD/SGD on overparametrized neural networks (e.g., Du al. (2018a;b); Allen-Zhu al. (2018); Zou et al. (2018); Jacot et al. (2018); Oymak& & Soltanolkotabi (2020), and many more). There are also convergence results that focus línear networks, without nonlinear activations (Bartlett al., 2018; Arora et al., 2019a; Wu et al.. 2019; Du & Hu, 2019; Hu et al., 2020). These results typically focus on the convergence of loss, hence do not address which of the many global minima is reached.
Another line of results tackles part (b), by studying the implicit bias or regularization of gradient- based methods on neural networks or related problems (Gunasekar et al., 2017: 201 80;;;;;; Arora et al., 2018; Soudry et al., 2018; Ji & Telgarsky, 2019a; Arora et al., 2019b; Woodworth et al., 2020; Chizat & Bach, 2020; Gissin et al., 2020). These results have shown interesting progress that even without explicit regularization terms in the training objective, algorithms such as GD applied on neural networks have an implicit bias towards certain solutions among the many global minima. However, in proving such results, many results rely convergence assumptions such global convergence of loss to zero and/or directional convergence of parameters and gradients. Ideally, such convergence assumptions should be removed because they cannot be tested priori and there are known examples where GD does not converge to global minima under certain initializations (Bartlett et al., 2018; Arora al., 2019a).
"Based on work performed during intersship Google Research

---

Published as a conference paper at ICLR 2021
Regression
Regression task, carphat
8
Figure 1: Gradient descent trajectories of linear coefficients of línear fully-connected, diagonal, and convolutional networks on a regression task, initialized with different initial scales a = 0.01, 1. Networks are initialized at the same coefficients (circles purple lines), but follow different trajec- tories due to implicit biases of networks induced from their architecture. The figures show that our theoretical predictions limit points (circles yellow line, the set of global minima) agree with the solution found by GD. For details of the experimental setup, see Section 6.
1.1 SUMMARY OUR CONTRIBUTIONS
We study the implicit bias of gradient flow (GD with infinitesimal step size) on linear neural net- works. Following recent progress on this topic, we consider classification and regression problems that have multiple solutions with zero training eπrоr. Our analyses apply to general class of net- works, and prove both convergence and implicit bias, providing more complete characterization of the algorithm trajectory without relying on convergence assumptions.
We propose a general tensor formulation of nonlinear neural networks which includes many network architectures considered in the literature. In this paper, focus the linear version of this formulation (i.e., no nonlinear activations), called linear tensor networks.
For linearly separable classification, we prove that linear tensor network parameters converge in direction to singular vectors of tensor defined by the network. As a corollary, we show that linear fully-connected networks converge to the & max- max-margin solution (Ji & Telgarsky, 2020).
For separable classification, decomposable (Assumption 1), the gradient flow finds the f2/depth max- max-mangin solution in the singular value space, leading the parameters converge to the top singular vectors of the tensor when depth = 2. This theorem subsumes known results on linear convolutional networks and diagonal networks proved in Gunasekar et al. (2018b), withou using convergence assumptions.
further show that if the linear tensor network is orthogonally
For underdetermined linear regression, we study the limit points of gradient flow on orthogo- nally decomposable networks (Assumption 1), and provide a full characterization of the limit points. This theorem covers results on deep matrix sensing (Arora et al., 2019b) as a special case, and extends a similar recent result (Woodworth et al., 2020) to broader class of networks.
For underdetermined linear regression with deep linear fully- connected networks, we prove that the network converges to the minimum f2 norm solutions as we scale the initialization to zero.
Lastly, we present simple experiments that corroborate our theoretical analysis. Figure I shows that our predictions of limit points match with solutions found by GD.
PROBLEM SETTINGS AND RELATED WORKS
We first define notation used the paper. Given a positive integer a, let [a] (1,...,, We use Ia to denote the d x d identity matrix. Given matrix A, we use vec( to denote its vectorization, all columns of A. For two vectors a and b. let a be their tensor product, O b be their element-wisg product, and a be the element-wise k-th power of a. Given order- --th element of A, where [L]. In element indexing, we use to denote all indices in the corresponding
i... the concatenation
tensor E Re x x..... k1, we use A ji....fr. to denote the (j1.j2.....
E [ky] for all dimension, and a b to denote all indices from a to b. For example, for matrix A, [A]. .466 denotes a submatrix that consists of 4th-6th columns of A. The square bracket notation for indexing overloads
2

---

Published as a conference paper at ICLR 2021
with [a] when a E N, but they will be distinguishable from the context. Since element indices start from 1, we re-define the modulo operation a mod d := a - |d E [d] for a > 0. We use ej to denote the j-th stardard basis vector of the vector space R Lastly, we define the multilinear multiplication between a tensor and linear maps, which can be viewed as a generalization of left- and right-multiplication
matrix. Given a tensor A E Ig x..kk,, and linear maps Bj E R for E [L]. we define the multilinear multiplication o between them as
A B T B ...... B = Σ Aimod [A Ir. (e) @ ... @ Ej (BT
B
Σ Sinngg [Ali.... Wi..i (Bie) 81 @ ... @ BLe R
2.1 PROBLEM SETTINGS
We are given dataset {(x;; v.)]==n where 2, E Ed and E R. We let X E Ruxd and y e R" be the data matrix and the label vector, respectively. We study binary classification and linear regression in this paper, focusing on the settings where there exist many global solutions. For binary classification, we assume 1/1 E [ and that the data is separable: there exists a unit vector z and a constant > 0 such that y: z 2 y for all i E [m]. For regression, we consider the underdetermined case (n < d) where there are many parameters E Rd such that X= y. Throughout the paper, we assume that X has full row rank.
We use f(:: +) I2d - R to denote a neural network parametrized by O. Given the network and the dataset, we consider minimizing the training loss (()) = اiー [xx;; θ), yi) over O Following previous results (e.g.. Lyu & Li (2020); Ji & Telgarsky (2020)), we use the exponential loss E(D. y) exp(- (opp(--y) ûy) for classification problems. For regression, we use the squared error loss L(j. y) ()- On the algorithm side, we minimize L usiing gradient flow, which can be viewed as GD with infinitesimal step size. The gradient flow dynamics defined as
de θ (e)
2.2 RELATED WORKS
Gradient flow/descent in separable classification. For linear models f(x; z) = xx= with sep- arable data, Soudry et al. (2018) show that the GD run on C drives ||=||| to co, but z converges in direction to the l max-margin classifier. The limit direction of is aligned with the solution of
minimiZezeR* ||||| subject to y 2 1 for i E [m),
(1)
where the norm in the cost is the le norm. Nacson al. (2019b;c); Gunasckar et al. (2018a); Ji & Telgarsky (2019b;c) extend these results to other (stochastic) algorithms and non-separable settings.
Gunasekar et al. (2018b) study the same problem on linear neural networks and show that GD exhibits different implicit bias depending on the architecture. The authors show that the linear coefficients of the network converges in direction to the solution of (1) with different norms: lg norm for linear fully-connected networks, f2/l (quasi-)norm for diagonal networks, and DFT-domain l2/L (quasi-)norm for convolutional networks with full-length filters. Here, T denotes the depth. We note that Gunasekar et al. (2018b) assume that GD globally minimizes the loss, and the network parameters and the gradient with respect the linear coefficients converge in direction. Subsequent results (Ji & Telgarsky, 2019a; 2020) remove such assumptions for linear fully-connected networks.
A recent line of results (Nacson et al., 2019a; Lyu & Li, 2020: Ji & Telgarsky, 2020) studies general homogeneous models and show divergence of parameters to infinity, monotone increase of smoothed margin, directional convergence and alignment of parameters (see Section 4 for details). Lyu & Li (2020) also characterize the limit direction of parameters as the KKT point of a nonconvex max- margin problem similar to (1), but this characterization does not provide useful insights for the functions f(: +) represented by specific architectures, because the formulation is in the parameter space O Also, these results require that gradient flow/descent has already reached 100% training accuracy. Although study more restrictive set of networks (i.e., deep linear), we provide more complete characterization of the implicit bias for the functions f(: θ), without assuming 100% training accuracy.
Gradient flow/descent in linear regression. It is known that for linear models f(x;z) = xTxx GD converges the global minimum that is closest in &2 distance the initialization (see e.g..
3

---

Published as a conference paper at ICLR 2021
Gunasekar al. (2018a)). However, relatively less is known for deep networks, even for linear networks. This is partly because the parameters do not diverge to infimity, hence making limit points highly dependent on the initialization; this dependency renders analysis difficult. A related problem of matrix sensing aims to minimize Σ==(v (v: (A,, W .... Wt)) over WI.... Wt E lRdxd is shown in Gunasekar al. (2017); Arora et al. (2019h) that if the sensor matrices A, commute and we initialize all Wi's to aI, GD finds the minimum nuclear norm solution as a + 0.
Chizat et al. (2019) show that if a network is zero initialization, and we scale the network output by a factor of a + co, then the GD dynamics enters a "lazy regime" where the network behaves like a first-order approximation at its initialization, as also seen in results studying kerne approximations of neural networks and convergence of GD in the corresponding RKHS (c.g.. Jacot et al. (2018)).
Woodworth et al. (2020) study linear regression with a diagonal network of the form f(;; +4, w-) x² (w w where w. and w- are identically initialized w+ (0) w- (0) = ort. The authors show that the global minimum reached by GD minimizes a norm- like function which interpolates between (weighted) & norm (a - 0) and Eg norm (a - oc). In our paper, we consider more general class of orthogonally decomposable networks, and obtain similar results interpolating between weighted & and f norms. We also remark that our results include the results in Arora et al. (2019h) as a special case, and we do not assume convergence to global minima, as done in Gunasekar et al. (2017); Arora et al. (2019b); Woodworth et al. (2020).
TENSOR FORMULATION OF NEURAL NETWORKS
In this section, we present general tensor formulation of neural networks. Given an input x E Rdd
the network uses a linear map M that maps æ to an order-L tensor M(x) E IR x where L 2 2. Using parameters ey E R& and activation o the network computes its layers as the following:
H (ax) @ (ax) (M1, Iaa....... IRC)) E xx* (x())) = @ (H/-( (vi, I ........., Ix))) E R.eeIxX..K for I = 2,..... 1, (2)
f(x: +) (z) o Vr. E R.
We use θ to denote the collection of all parameters (U) (U)...., Uz). We call M(x) the data tensor. Although this new formulation may look bit odd in the first glance, is general enough to capture many network architectures considered in the literature, including fully-connected networks, diago- nal networks, and circular convolutional networks. We formally define these architectures below.
Diagonal networks. An I--layer diagonal network is written
fdiag (x:; Oding) = ó(. @(0(x ④ wi) O w2) O WL-1)"'w. WL,
(3)
where wy E Rdd for 1 E [Z]. The representation of faing as the tensor form (2) is straightforward. Let Maing (x) E Rdx-.xd x have MMasag j.j....... [>];, while all the remaining entries of Maiag (x) are
set to zero. We can set Vi = wi for all 1, and M Maiag to verify that (2) and (3) are equivalent.
Circular convolutional networks. The tensor formulation (2) includes convolutional networks fooa (o; (conv)) = d( -.. 00t.-/(((000 ww) w2) ... wt-1)) WL.
(4)
where wi E R with ki S d and kL = d, and defines the circular convolution: for any a E IR and
E R (k S d), we have a * nd defined as [a * b]: = ΣØ 1 [a] mod a [bb] for E [d]. Define Moonv (a:) X as |Meonv (aonv(x)))) Ja....u = [a) (E)n (t1+)) mod for ji [k]]
I E [Z]. Setting is = wi and Mconv, we can verify that (2) and (4) are identical.
Fully-connected networks. An L-yeer fully-connecter network is defined as
fi; Oc,) = o( - 000(0" W1) ... WL-1)WL.
(5)
where W. E d for / E [L 1] (we use di d) and wy, RRd. One can represent fro as the tensor form (2) by defining parameters 22 = vec (W)) for 1 E [L - 1] and 1y = Wp, and constructing the tensor (x) by recursive "block diagonal" manner. For example, if L = 2, can define (x) E di Xd2 to be the Kronecker product of Id, and æ. For deeper networks, we defer the full description of (x) to Appendix B.
4

---

Published as a conference paper at ICLR 2021
Our focus: linear tensor networks. Throughout this section, have used the activation ø to motivate our tensor formulation (2) for neural networks with nonlinear activations. For the remaining of the paper, we study the case whose activation is linear, ie., @(t) t. In this case,
f(:; ) ((x) (V1, ........ vL).
We will refer to (6) as linear tensor networks, where "linear" is to indicate that the activation is linear. Note that as a function of parameters vi,...; Vr,, I (a;; )) fact multilinear. We also remark that when depth I. 2. the data tensor M(x) is h1 x k2 matrix and the network formulation boils down to f(;; ) = o ((x)) )
Since the data tensor M(x) is a linear function of the linear tensor network is also linear function of æ. Thus, the output the network can also be written as / (ax )) = x² (()), where (()) E Rd denotes the linear coefficients computed as function of the network parameters @ Since the linear tensor network f(x: () is linear in æ, the expressive power of f is at best a linear model x + x² However, even though the models have the same expressive power, their architectural differences lead to different implicit biases in training, which is the focus of our investigation in this paper. Studying separable classification and underdetermined regression is useful for highlighting such biases because there are infinitely many coefficients that perfectly classify or fit the dataset.
For our linear tensor network, the evolution of the parameters by via gradient flow reads
= C(O) - - E (f(( +). y. Max.)) 00......1-11. Iu 11+1 UL) M x² (1). 11 IR 01 Up), AI E [Z].
where we initialize 2i att, for I E [L]. We refer and in the initial scale and initial direction, respectively. We note that we do not restrict By 's to be unit vectors, in order to allow different scaling (at initialization) over different layers. The vector E IR" is the residual vector, and each component of r is defined as
{ expp-xx.. +))
for classification,
[r]: ((((;;
( Q) yi
for regression.
4 IMPLICIT BIAS OF GRADIENT FLOW IN SEPARABLE CLASSIFICATION
In this section, present our results the implicit bias of gradient flow in binary classification with linearly separable data. Recent papers (Lyu & Li, 2020; Ji & Telgarsky. 2020) on this separable classification setup prove that after 100% training accuracy has been achieved by gradient flow (along with other technical conditions), the parameters of I-homogeneous models diverge to infinity, while converging in direction that aligns with the direction of the negative gradient. Mathematically.
[O(t)l 00, lim tu0
lim
+ (+) pii
- lim v e ((0
-1
Since the linear tensor network satisfies the technical assumptions the prior works, we apply these results to our setting and develop a new characterization of the limit directions of the parameters. Here, we present theorems on separable classification with general linear tensor networks. Corollar- ies for specific networks are deferred to Appendix A.
4.1 LIMIT DIRECTIONS OF PARAMETERS ARE SINGULAR VECTORS
Consider the singular value decomposition (SVD) of a matrix A = ΣØ= (y @ vj)) where m is the rank of A. Note that the tuples (u,, Uj, 8;) are solutions to the system of equations su AA and su ATuu. u. Lim (2005) generalizes this definition of singular vectors and singular values higher-order tensors: given an order-L tensor A E xgxxxxxx we define the singular vectors u1, U2, ... ur and singular value to be the solution of the following system of equations:
sui A (ui,.... W1 IN, u1.1.... ut), for I E [L].
(
Using the definition of the singular vectors of tensors, we can characterize the limit direction of parameters after reaching 100% training accuracy. In Appendix C, we prove the following:
5

---

Published as a conference paper at ICLR 2021
Theorem 1. Assume that the gradient flow satisfies ((o())) < for some to 2 0 and X" converges in direction, say u := lim x r(t) XTr(tt)la* Then, U,,..., Uy converge to the singular
vectors of (o)
For this theorem, we make some convergence assumptions, because the network is fully general; this is the only result where we assume convergence. fact, for the special case of linear fully- connected networks, the directional convergence assumption is not required, and the linear coef- ficients (tc(Osc) converge in direction to the & max-margin classifier. We state this corollary in Appendix A.1; this result also appears in Ji & Telgarsky (2020), but provide an alternative proof.
4.2 LIMIT DIRECTIONS FOR ORTHOGONALLY DECOMPOSABLE NETWORKS
Admittedly, Theorem I is not a full characterization of the limit directions, because there are usu- ally multiple solutions that satisfy (8). For example, in case of L 2, the data tensor (( is matrix and the number of possible limit directions (up to scaling) of (v1, U2) is at least the rank of m- Singular vectors of high order tensors are much less understood than the ma- trix counterparts, and are much harder to deal with. Although their existence is implied from the variational formulation (Lim, 2005), they are intractable to compute. Testing if a given number singular value, approximating the corresponding singular vectors, and computing the best rank-1 approximation are all NP-hard (Hillar & Lim, 2013); let alone orthogonal decompositions.
Given this intractability, it might be reasonable make some assumptions the "structure" of the data tensor M(z), so that they are easier to handle. The following assumption defines a class of orthogonally decomposable data tensors, which includes linear diagonal networks and linear full-length convolutional networks as special cases (for the proof, see Appendix D.2 and D.3).
For the data tensor M(x)) E Rkix-- of a linear tensor network (6), there exist full column rank matrix S E Cm (d < m S min; ki) and matrices Un E Ckixm. "e....... Uy, E Ck xm such that U Ui = Im for all I E [L], and the data tensor M(x) can be written as
Assumption 1.
((x) = Σ | ((U)) @ (U2) 8 3 (U2)-5)-
In this assumption, we allow UI.... UL and S to be complex matrices, although M(x) and param- eters 2i stay real, defined earlier. For complex matrix A, complex conjugate, A" to denote its transpose (without conjugating), and A Sf to denote its conju- gate transpose. In case of L, 2, Assumption requires that the data tensor M(x)) (now matrix) has singular value decomposition M(x) = Un diag Sx Sr)UU i.e., the left and right singular vectors are independent of æ. and the singular values are linear æ. Using Assumption 1, the following theorem characterizes the limit directions.
A to denote its entry-wiss,
Theorem 2. Suppose a linear tensor network satisfies Assumption 1. If there exists X > 0 such that the initial directions B1,..., dz of the network parameters satisfy [ o1,,1 IU, o 2 Xfor all I E [L 1] and j E [m], then ((@(t)) converges in direction that aligns with S pe,, where p E C denotes a stationary point of the following optimization problem
minimizepEc" ||p||æ/1 subject to y: ST p2 ST e
If S invertible, then ((O(I)) converges in direction that aligns with a stationary point 80 of
minimizozER ||S-T =112/1
subject to ya z 2 1, Vi ViEl [m].
Theorem 2 shows that the gradient flow finds sparse 8d that minimizes the l2/L norm in the "sin- gular value space," " where the data points æ; are transformed into vectors Sx, consisting of singular values of M(x.). Also, the proof of Theorem 2 reveals that in case of L = 2, the parameters vy(t) in fact converge to the top singular vectors of the data tensor M M(-X""
x""r) r); thus, compared to Theorem 1, complete characterization of "which" singular vectors to converge to.
have
The proof of Theorem 2 is in Appendix D. Since the orthogonal decomposition (Assumption 1) of M(x:) tells us that the singular vectors M(x) in UI...., UL are independent of æ, we can transform the network parameters v, to U/ v, and show that the network behaves similar to a linear diagonal network. This observation comes in handy in the characterization of limit directions.

---

Published as a conference paper at ICLR 2021
Remark 1 (Necessity of initialization assumptions), In order to remove the assumption that the loss converges to zero, at least some condition on initialization is necessary, because there are exam- ples showing con-convergence of gradient flow for certain initializations (Bartlett et al., 2018; Arora et al., 2019a). In our theorems, we pose assumptions on initial directions in that are sufficient con- ditions for the loss (t)( converge zero. Although such sufficient conditions are "stronger" than assuming (t) - O, they are useful because they can be easily checked a priori, i..., before running gradient flow. We note an important fact that in Theorems 2 and onwards, the conditions on initialization are used solely to prove convergence of the loss to zero, and our statements on the implicit bias hold whenever the loss converges to zero, even for initializations that do not satisfy our conditions. In addition, we argue that our assumptions are not too restrictive; À can be arbitrarily small, so the conditions are satisfied with probability / if we set öt, = and randomly sample other it s.. Setting one layer to zero to prove convergence is also studied in Wu et al. (2019). Lastly, the condition that Ur is "small" can be replaced with any layer: c.g., convergence still holds if |[U 1 I[U? d1l 2 2 À for all / = 2..... L and j [m]]
Remark 2 (Comparison to existing results). Theorem leads to corollaries (stated in Appendix A.2) on linear diagonal and full-length convolutional networks, showing that diagonal (or convolutional) networks converge to the stationary point of the max- max-margin problem with respect to the l2 norm (or DFT-domain E2/L norm). Theorem recovers the results in Gunasekar et al. (2018b) without relying on assumptions such as directional convergence of parameters and gradients.
Remark 3 (Implications to architecture design). Theorem 2 shows that the gradient flow finds solution that is sparse a "transformedd input space where all data points are transformed with S. This implies something interesting about architecture design: if the sparsity of the solution under certain linear transformation T is needed, one can design a network using Assumption 1 by setting S = T. Training such a network will give us a solution that has the desired sparsity property.
Other than Assumption 1, there is another setting where we can prove a full characterization of limit directions: when there is one data point (n 1) and the network is 2-layer (L = 2). This "extremely overparametrized" case is motivated by an experimental paper (Zhang et al., 2019) which studies generalization performance of different architectures when there is only one training data point.
Theorem 3. Suppose we have a 2-layer linear tensor network (6) and a single data point (æ, y). Consider the compact SVD M(x) = Un diag(s)U?, where U1 B U2 k and 8 E Rd for m S minnki k2) Let pa0 E E.T be a solution of the following optimization problem minimizeppE?.
||ell subject to ys" p p21.
Assume that there exists X >> 0 such that the initial directions 01, 02 of the network parameters satisfy [U 0113 [U] 02]3 2 X for all j E [m]] Then, Vi and U2 converge in direction i
and U where |n! = m 0000 01/22 and sign(n)))) sign(y) @ sign(n)))
The proof of Theorem 3 can be found in Appendix E. Since ~. is the minimum & norm solution in the singular value space, the parameters vn and V2 converge in direction to the top singular vectors. We would like to emphasize that this theorem can be applied any network architecture that can be represented as linear tensor network. Recall that the previous result (Gunasekar et al., 2018b) only considers full-length filters (k) d), hence providing limited insights on networks with small filters, e.g., k1 = 2. In light of this, we present a corollary in Appendix A.3 showing that linear coefficients of convolutional networks converge in direction "filtered" version of x.
IMPLICIT BIAS OF GRADIENT FLOW IN UNDERDETERMINED REGRESSION
In Section 4, the limit directions of parameters we characterized do not depend on initialization. This is due to the fact that the parameters diverge to infinity in separable classification problems, so that the initialization becomes unimportant in the limit. This is not the case in regression setting, because parameters do not diverge to infinity. As we show in this section, the limit points are closely tied to initialization, and our analyses characterize the dependency between them.
5.1 LIMIT POINT CHARACTERIZATION FOR ORTHOGONALLY DECOMPOSABLE NETWORKS
For the orthogonally decomposable networks satisfying Assumption with real S and U,'s, we consider how limit points of gradient flow change according initialization. We consider a specific
7

---

Published as a conference paper at ICLR 2021
initialization scheme that, in the special case of diagonal networks, corresponds setting (7) aw for I E [L- 1] and (0) =0. We use the following lemma on relevant system of ODEs:
Lemma 4. Consider the system of ODEs, where p, q R - R: /=p²- p(0) =1, 1, (0)= =.
p=pt-
Then, the solutions pr.(() and (r.(1) are continuous on their maximal interval of existence of the form (-e,c) C R for some e E (0, oo]. Define (1) = pr. (1)(1)=-1gg (1); then, h1,()) is odd and strictly increasing, satisfying limate (t) = oo and lime-e h1(() -x.
Using the function (t) from Lemma 4, we can obtain the following theorem that characterizes the limit points as the minimizer of norm- -ike function QL.a.n among the global minima.
Theorem 5. Suppose linear tensor network satisfies Assumption I. Assume further that the matri- ces U1...., UL and S from Assumption I are all real matrices. For some X > 0, choose any vector n RTM satisfying [m]] 2 X for all j E [m]] and choose initial directions ii Umi for E [L-1] 1] and Uy = 0. Then, the linear coefficients (()(t)) converge to S p0 where pde is the solution of
minimizepeRs PERm
QLaan(() = a² Σ [
[ply [-
subject to XST p y,
where QL, Imm + R is norm-like function defined using Hy(t) = So (T)d7. If S is invertible, then B(O(t)) converges the solution = of
minimizezeRd
QL. (S..,((S-22)) 22) subject to X==
The proofs of Lemma 4 and Theorem are deferred to Appendix
Remark 4 (Interpolation between & and f2). It can be checked that (!) grows like the absolute
value function if t large, and grows like a quadratic function if l is close to zero. This means that
lim (p) -0
lim (p. a000
2
(0)
so QL,a. interpolates between the weighted & and weighted &g norms of p. Also, the weights in the norm are dependent on the initialization direction nj unless L = 2 and a + O. In general, Qr.a.; interpolates the standard & and & norms only if [ is the same for j E [m]. This result is similar to the observations made in Woodworth et al. (2020) which considers diagonal network with a "differential" structure f(x; W4, w-)- x=' (w L "h In contrast, our results apply to a more general class of networks, without the need to have the differential structure. In Appendix A.4, we state corollaries of Theorem 5 for linear diagonal networks and linear full-length convolutional networks with even data points. There, we also show that deep matrix sensing with commutative sensor matrices (Arora et al., 2019b) is special case of our setting.
Next, present the regression counterpart of Theorem 3, for 2-layer linear tensor networks with a single data point. For this extremely overparametrized setup, we can fully characterize the limit points as functions of initialization di (0) aU and (0) = ar22, for any linear tensor networks including linear convolutional networks with filter size smaller than input dimension.
Theorem 6. Suppose we have a 2-layer linear lensor network (6) and a single data point (x, v). Consider the compact SVD M(x) = U, diag(()U55 where U, E T& xm, U2 E k and E R for m S min(k1, k-). Assume that there exists X >> 0 such that the initial directions 01. U2 of the network parameters satisfy [UT 0113 [ 521 Z X for all j E [m]. Then, gradient flow converges to a global minimizer of the loss L, and vı (t) and vz(t) converge to the limit points:
R&xx,,
(Uf =au
01 @ cosh (g-1
y1
s)
+ Uf 02 O sinh (g-1
y
8)
+ +a - U,UF)
2
a
S = =a22 UU 01 O sinh (g (g-1(2)
+ U 82 @ cosh g
8)
-U,
az
az
where y- is the inverse of the following strictly increasing function
g(v) Σ m _m [s]s
(VT + ozl sinh(2isl,u) + IU bil ozl, cosh(2(s))zz)
The proof can be found in Appendix G. We can observe that as a + 0. we have g (-)) xo. which results in exponentially faster growth of the sinh(.) and cosh(-) for the top singular values. As a result, the top singular vectors dominate the limit points of and vz" as a - 0, and they do not depend on the initial directions 11 02. Experiment results in Section 6 support this observation.
8

---

Published as a conference paper at ICLR 2021
5.2 IMPLICIT BIAS FULLY- CULLY-CONNECTED NETWORKS: THE 0 LIMIT
We state our last theoretical element of this paper, which proves that the linear coefficients Bic (c of deep linear fully-connected, networks converge to the minimum & norm solution as a - 0. We assume for simplicity that d1 = d2
= dr. = d in this section, but we can extend it for di 2 without too much difficulty. Recall (x; Oe) = x: W
Wi-1 w. We minimize the training loss with initialization (i) = a WW for E [L - 1] and wt (0) = L.ü
Theorem 7. Assume that initial directions WI...., WL-1 11 satisfy (1) W W WI+
for E [L- and (2) there exists À > 0 such that W L w d ML. Then, the gradient flow converges to a global minimum, and li lim (0 = X X"(Xx")-
The proof is presented in Appendix H. Theorem 7 shows that in the limit - O, linear fully- connected networks have bias towards the minimum lz norm solution, regardless of the depth. This is consistent with the results shown for classification. We also note that the convergence to a global minimum holds for any a > 0, and our sufficient conditions (W,' Wi x W4+1 Wit and WT-, W-11- - w > ATa) for global convergence is generalization of the zero-asymmetric initialization scheme (W1 = WL-1 = Ia and w 0) proposed in Wu et al. (2019).
EXPERIMENTS
Regression. To fully visualize the trajectory of linear coefficients, we run simple experiments with 2-layer linear www.-oontee//lgggo////ooooiiiiie
networks with a single 2-dimensional data point (x. y) = ([1 2). For this dataset, the minimum E2 norm solution (corresponding to fully-connected networks) of the regression problem is [0.2 0.4). whereas the minimum & norm solution (corresponding to diagonal) is [0 0.5) and the minimum DFT-domain L norm solution (corresponding to convolutional) is [0.33 0.33]. We randomly pick four directions 2 21 IR?, and choose initial directions of the network parameters in a way that their linear coefficients at initialization exactly ((O(0))
a² zj- With varying initial scales E {0.01, 005,, 1), we GD with small step size 10 for large enough number of iterations T = 5 x 10S. Figures I and 2 plot the trajectories of (()) (appropriately clipped for visual clarity) as well as the predicted limit points (Theorem 6). We observe that even though the networks start at the same linear coefficients a zj. they evolve differently due to different architectures. Note that the prediction of limit points is accurate, and the solution found by GD is less dependent on initial directions when a is small.
Classification. It is shown in the existing works as well as in Section 4 that the limit directions of linear coefficients are independent of the initialization. Is this also true in practice? To see this, we run a set of toy experiments on classification with two data points (#1. ([1 2], +1) and (I2,, 322) ([0 3], 11). One can check that the max-margin classifiers for this problem are in the same directions to the corresponding min-norm solutions in the regression problem above. We use the same networks as in regression, and the same set of initial directions satisfying (0)) = a² a²zz- With initial scales E (0.01, 0.5, 1}. we run GD with step size 7) = 5 x 10-1 for T 2 x 10th iterations, All experiments reached (()) S 10-5 at the end. The trajectories are plotted in Figure 2 in the Appendix. We find that, in contrast to our theoretical characterization, the actual coefficients are quite dependent on initialization, because we do not train the network all the way to zero loss. This observation is also consistent with a recent analysis (Moroshko et al., 2020) for diagonal networks, and suggests that understanding the behavior of iterates after a finite number of steps is an important future work.
7 CONCLUSION
This paper studies the implicit bias of gradient flow on training linear tensor networks. Under general tensor formulation of linear networks, we provide theorems characterizing how the network architectures and initializations affect the limit directions/points of gradient flow. Our work provides a unified framework that connects multiple existing results on implicit bias of gradient flow as special cases.

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 039662, 2018.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pp- 244-253, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. convergence analysis of gradient de- scent for deep linear neural networks. In International Conference on Leurning Representations, 2019a.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pp. 7413-7424, 2019b.
Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initialization effi- ciently learns positive definite linear transformations by deep residual networks. In International Conference Machine Learning, pp. 111-55115550 -300, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.004486, 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances Neural Information Processing Systems, pp. 2937-2947, 2019.
Simon S Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. arXiv preprint arXiv:1901.08572 2019.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global 2018a.
minima of deep neural networks. arXiv preprint arXiv:
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv: 2018b.
Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. In International Conference on Learning Representations, 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli,, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference Machine Learning, pp. 1832- 1841, 2018a.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471, 2018b.
Christopher J Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in opti- mizing deep linear networks. In International Conference Learning Representutions, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019a.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Learning Theory, pp. 1772-1798, 2019b.
10

---

Published as a conference paper at ICLR 2021
Ziwei Ji and Matus Telgarsky. A refined primal-dus analysis of the implicit bias. arXiv preprint arXiv:1906.045400 2019c.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.0660 2020.
Lek- Lek-Heng Lim. Singular values and eigenvalues of tensors: variational approach. In /st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005., pp. 129 132. IEEE, 2005.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D) Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. arXiv preprint arXiv:2007.065 06738, 2020.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry, Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pp. 4683-4692, 2019a.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420-3428. PMLR, 2019b.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3051-3059, PMLR, 2019c.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameteriiation: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference On Learning Theory, 2020.
Lei Wu, Qingcan Wang, and Chao Ma. Global convergence of gradient descent for deep linear residual networks. In Advances in Neural Information Processing Systems, pp. 13389-13398, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Michael C Mozer, and Yoram Singer. Identity crisis: Memorization and generalization under extreme overparameteriiatton. arXiv preprint 1rXiv:1902.04668, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint arXiv:1811.088. 2018

---

Published as a conference paper at ICLR 2021
togress laok,
1300
8
cassiicatin Teak: rital scale (aghaa C5
Claarication Tade latl sca telcha = 1D
Figure 2: Gradient descent trajectories of linear coefficients of linear fully-connected. diagonal, and convolutional networks on regression task with initial scale = 0.5 (top left), and networks on classification task with initial scales 0.01, 0.5, (rest). Networks are initialized at the same coefficients (circles purple lines), but follow different trajectories due to different implicit biases of networks induced from their architecture. The top left figure shows that our theoretical predictions on limit points (circles yellow line, the set of global minima) agree with the solution found by GD. For details the experimental setup, please refer to Section 6.
A COROLLARIES ON SPECIFIC NETWORK ARCHITECTURES
We present corollaries obtained by specializing the theorems in the main text to specific network architectures. We briefly review the linear neural network architectures studied in this section.
Linear fully-connected networks.
An L-layer linear fully-connected network is defined as fıc(:; θc.) = x W WL-1W1,
(10)
where Wi Rd for I [L 1] (we d d) and wL R.d
Linear diagonal networks. An L-layer linear diagonal network is written as
fdiag( Oding) = (x O wi
wT-11) WT.
(1I)
where wy E Rdd for E [L].
Linear (circular) convolutional networks. An L-layer linear convolutional network is written
Seonv (æ:; @ (... ((x: wi) W2) w "
(12)
where wi E R with ki d and ky d, and defines the circular convolution: for any Rd
and # < d), have a+b 12d defined as [a+b]. - mod e[b]j- for [d].
In case of k, for all I [L], we refer to this network as full-length convolutional networks.
Deep matrix sensing. The deep matrix sensing problem considered in Gunasekar et al. (2017);
Arora et al. (2019b) aims to minimize the following problem
minimize Wi... ax
Lms ...... ..M) Σn_
- (us (A, W WI))
(13)
where the sensor matrices A,...,A, An
ddxd are symmetric. Following Gunasekar et al. (2017); Arora et al. (2019b), we consider sensor matrices A A A, E dd that commute. To make the problem underdetermined, assume that < d, and A, 's linearly independent.
12

---

Published as a conference paper at ICLR 2021
A.1 COROLLARY OF THEOREM
Corollary 1. Consider an L-layer linear fully-connected network (10). If the training loss satisfies L(Oro(la) < for some to 2 then (I)()(() converges in direction that aligns with the solution of the following optimization problem
minimize =ER
||=1|/ subject to 2 12221, Vi E
Corollary 1 shows that whenever the network separates the data correctly, the linear coefficients (to(Otc) convergence in direction to the Eg max-margin classifier. Note that this corollary does not require the directional convergence of XTr, which is different from Theorem 1. In fact, this corollary also appears in Ji & Telgarsky (2020), but we provide an alternative proof based on our tensor formulation. The proof of Corollary I can be found in Appendix C.
A.2 COROLLARIES OF THEOREM 2
Corollary 2. Consider an L-layer linear diagonal network (11). If there exists X > 0 such that the initial directions w....., Wr of the network parameters satisfy [w:]] -[wr] 2 for all E [L-1] 1] and] j [d], then Baiag O diag converges a direction that aligns with stationary point = of
minimizezeRd
|
subject to y x 2 1, vi [n]]
For full-length convolutional networks, we define F Cdxd be the matrix of discrete Fourier transform basis [F Va exp( -app--/I12201 / Note that F = F-1, and both F and F symmetric, but not Hermitian.
Corollary 3. Consider an L-layer linear full-length convolutional network (12). If there exists À > O such that the initial directions Wi...., W of the network parameters satisfy [[Fwi])] [[F ' X for all I E [T.-1] and E [d], then Beonv ( (Qconv(t) converges in direction that aligns with a stationary point 00 of
minimizezERd
F21lz/L subject to y 2 2 1, Vi ViE [n].
Corollary 2 shows that in the limit, linear diagonal network finds sparse solution that is sta- tionary point of the l2/L max-margin classification problem. Corollary 3 has a similar conclusion except that the standard f2/L norm replaced with DFT-domain l2 norm. By specifying mild conditions on initialization (see Remark 1), these corollaries remove the convergence assumptions required in Gunasekar et (2018b). The proofs of Corollaries 2 and 3 are Appendix D.
A.3 COROLLARY OF THEOREM 3
Recall that Theorem 3 can be applied to any 2-layer networks that can be represented linear tensor networks. Examples include the convolutional networks that are not full-length (i.e., filter size kn < d), which are not covered by the previous result (Gunasekar et al., 2018b). Here, we present the characterization
convergence directions of Bronv @conv (f)) for small-filter cases:
k = and b1 2.
Corollary 4. Consider a 2-layer linear convolutional network (12) with k = and a single data point (x. v). there exists X O such that the initial directions wi and w of the network parame- ters satisfy |==l| oi (x" 02) )2 ||>]| X, then Beouv ( conn (t)) converges in direction that aligns
with ya.
Consider a 2-layer linear convolutional network (12) with kn- and a single data point (æ, v). Let & := [|z]] ... [æ]a [x]]], and z := [[=]a [x]] ... [==]--]. 1). If there exists X > 0
such that the initial directions W0 and Wh of the network parameters satisfy
((x T )2
((x '0 02
([bz)1 + (012))²
- 2 + - 2 X, and ((0,) - (011))
2
X,
x 2
x
T
then Boonv 4 oonvv (t)) converges in a direction that aligns with a a.fiitered version of o::
Bonny conv (t))
(2yæ + y ' + y के
if 0,
lim
Beonv cony (t))
x
2yæ - y x y tे
if < 0.
13

---

Published as a conference paper at ICLR 2021
Corollary 4 shows that if the filter size is k1 1. then the limit direction of Bzonv (2 conv)) is always the lg max max-margen margin classifier. Note that this is quite different from the case k = which converges to the DFT-domain ε max-mnagiin classifier. However, for < k < d, it is difficult to characterize the limit direction as the max-margin classifier some common norms. Rather, the limit directions of ( correspond to a "filtered" version of the data point, and the weights of the filter depend on the data point æ. For L = 2, the filter is a low-pass filter if the autocorrelation x' x of is positive, and high-pass if the autocorrelation is negative. For k 2, the filter weights are more complicated to characterize in terms of æ, and the filter length increases as k1 increases. We prove Corollary in Appendix E.
A.4 COROLLARIES OF THEOREM
In this subsection, we apply Theorem 5 to linear diagonal networks, linear full-length convolutional networks with even data, and deep matrix sensing. The proofs of the corollaries can be found in Appendix F.
Corollary 5. Consider an L-layer linear diagonal network (11), For some À > 0, choose any vector w E I& satisfying [w]] 2 for all E [d]. and choose initial directions
w for I [L 1]
and w1= O. Then, the linear coefficients Baiagl @diag (t)) converge the solution n0xh of
men QL.,,o(2): = a²
HL
subject to
X - y.
Recall that the original statement of Assumption 1 allows the matrices S, U....., U2 be com- plex, but Theorem 5 poses another assumption that these matrices are real. In applying Theo- rem 2 to convolutional networks get Corollary 3, we used the fact that the data tensor Moonv (2:) of linear full-length convolutional network satisfies Assumption I with S = d F and U1
UL F", where F Cd is the matrix of discrete Fourier transform basis [F] Vd exp( - and F" the complex conjugate of F. Note that these are complex matrices, so one cannot directly apply Theorem to convolutional networks. However, turns out that if the data and initialization are even, we can derive a corollary for convolutional networks.
We say that vector is even when it satisfies the even symmetry, in even functions. More con- cretely, vector æ E I is even if [æ]5+2 [m]a-j for j = 0, O,..., Id-3 J; i.e., the vector has the even symmetry around its "origin" [m]1. From the definition of the matrix F E Cdxd it is straight- forward to check that æ is real and even, then its DFT Fx is also real and even (see Appendix F.4 for details).
Corollary 6. Consider an L-layer linear full-length convolutional network (12). Assume that the data points {x,)? are all even. For some X >> O, choose any even vector w satisfying [Fwl] 2 X for all j E [d], and choose initial directions w V for E [L 1] and w 0. Then, the linear coefficients Beonv (O (t)) converge to the solution z of
QL. (Fz) (Fz)) a² Σ [
[F [F
minimize ZERR even
subject to
Xz = y.
Corollaries and show that the interpolation between minimum weighted & and weighted & so- lutions occurs for diagonal networks, and also for convolutional networks (in DFT domain, with the restriction of even symmetry). The conclusion of Corollary is similar to the results in Woodworth et al. (2020), but the network architecture (11) considered in our corollary is slightly different from the "differential" network fæ; w., w-) = x _T (w w
o ) in Woodworth et al. (2020).
As mentioned in the main text, we can actually show that the matrix sensing result in Arora et al. (2019b) is a special case of our Theorem 5. Given any symmetric matrix M e Rdxd let eig(M) e Rdd be the d-dimensional vector of eigenvalues of M.
Corollary 7. Consider the depth-L deep matrix sensing problem (13). Let A,'s be symmetric, and
assume Az,..., ,, An commute. For a >> choose initialization Wi(0) = aIa for E [T. and
(0) = 0. Then, the product (t( (t( converge to the solution M of
minimize
(Lig(ei = a Σ j=1
Hi.
[eig[M]], L
subject to (ma(M) = 0.
MeRexd, symmetric
14

---

Published as a conference paper at ICLR 2021
Under additional assumption that A,'s are positive semidefinite, Theorem 2 in Arora al. (2019b) studies the initialization () = ald for all I E [L], and shows that the limit point of W.... Wi converges to the minimum nuclear norm solution of positive definiteness of A, 's and let (0) = 0, to show a complete characterization lution found by gradient flow, which interpolates between the minimum nuclear norm (i.e., Schatten 1-norm) solution (when a + 0) and the minimum Frobenius norm (i.c., Schatten 2-norm) solution (when + 00).
- O. We remove the assumption
the so-
B TENSOR REPRESENTATION OF FULLY-CONNECTED NETWORKS
In Section 3, we only defined the data tensor (xx of fully-connected networks for L = 2. Here, we describe an iterative procedure constructing the data tensor for deep fully-connected networks.
We start with Ti [1)
E RR Next, define a block diagonal matrix T2(x) E (gd1dxxds where the "diagonals" (T(xx) (nd (x) for j E [dz], while all the other entries are filled with O. We continue this "block diagonal" procedure, as the following. Having defined 1 Rdid2 de x.xxxxxxx x.xxxxxxiii-- -id--d--xdd--
1. Define (()) E Rdid x
2. Set (Tr 10 1---1)) 111:-1155 Ti-1 Vj [d]].
3. Set all the remaining entries of (x)x) to zero.
We repeat this process for 2,..., L, and set (.) of the tensor formulation ty = vec( Wi) for I E [L 1] and vz = wr, and using the tensor M(x) (æ)), we can check the equivalence of (2) and (5).
T Txx). By defining the parameters
C PROOFS OF THEOREM AND COROLLARY
C.I PROOF OF THEOREM 1
The proof of Theorem is outlined as follows. First, using the directional convergence and align- ment results in Ji & Telgarsky (2020), we prove that each of our network parameters vi converges in direction, and it aligns with its corresponding negative gradient V. Then, we prove that the directions of ey's are actually singular vectors of M( 20), where x == lim x(r(t)
|xTr())2
Since a linear tensor network is an L-homogeneous polynomial of U1...., Uz it satisfies the as- sumptions required for Theorems 3.1 and 4.1 in Ji & Telgarsky (2020). These theorems imply that the gradient flow satisfies L(O (fn) < 1 for some to 2 0, then (tt) converges direction, and the direction aligns with - V (t)); that is,
(t)
(())))((((()
lim |0())22 = co, lim +20
lim t00
@00 = -1
(14)
(1)]2
For linear tensor networks (6), the parameter @ is the concatenation of all parameter vectors Vi. UL, so (14) holds for O [o.
"
Now, recall that by the definition of the linear tensor network, we have the following gradient flow
M
XTr (vi,...; 0/-1, Ik 0141,..., vt).
Note that we can apply this to calculate the rate of growth of ||0:1
d 1 - = 20 in = 20 M - x- a (Vi...., U Ik, U1+ U141,...
dt
11 vi, ...,,.., v1.) 2M (M(--"rr) (Vi,..., ,
di 1//r0111 for any 1' E [4].
15

---

Published as a conference paper at ICLR 2021
so the rate at which | grows over time is the same for all layers / E [L]. By the definition of θ and (14), we have
00,
which then implies
(+ 1 [t)
( VL.
lim [11(()) + oo,
lim E
for all 1 E [T.]. Now, let I be the set of indices that correspond to the components of by in θ. follows from (14) that
vt(() lim (x)(1)
(t)
(
10 (0(12 [1)( +o
lim (t)
lim 2200
vI
+0000
( O
(0)l2
thus showing the directional convergence of uy s.
Next, it follows from directional convergence of θ and its alignment with ((e(()) (14) that Ve((O) also converges direction, in the opposite direction of O. By comparing the components in It's, we get that V [(@) converges in the opposite direction of er.
For any / E [L], now let of lim
vt(t)
Also recall the assumption that X (t)) converges
(f)ll
x" r(t) be the limit direction. By the gradient
in direction; let the unit vector u == lim X r(02
flow dynamics of vt, we have
vi x [ = ((-u)) (vf
Vi INy v vf.),
for all I E [L]. Note that this equation has the same form (8), the definition of singular vectors in tensors. So this proves that (vf ,..., Vy) are singular vectors of ((-u²).
C.2 PROOF OF COROLLARY
The proof proceeds follows. First, will show using the structure of the data tensor Mr. that the limit direction of linear coefficients (r.(O is proportional to o where e is a nonzero scalar and 00 is the limit direction of XTr. Then, through a closer look at u and c, we will prove that Bic ic) is in fact conic combination of the support vectors (i.e., the data points with the minimum margins). Finally, we will compare 3ic (Ope with the KKT conditions of the E2 max- margin classification problem and conclude that Pio O must be in the same direction the l max- max-margin classifier.
Due to the way how the data tensor Mie is constructed for fully-connected networks (Appendix B), we always have
x 0
X
0
Vv, = Mic(-X (Kky, U2.... .,,...,,)) vz) span
From Theorem 1, have directional convergence of 02 and its alignment with V ((,)). This means that the limit direction vfo, which is a fixed vector, must be also in the span of vectors written
above. This implies that X r must also converge to some direction, say u == lim; |X 1 r
x()(t)
Now recall the definition of V1 in case of the fully fully-conneeted network: U1 vec (1c. So, by reshaping of into its original d1 x d2 matrix form W we have
u q"
for some q Rd, This implies that the linear coefficients Bie (Ote) of the network converge in direction to
BiG + fc
W
W W 00 W
W wf
cu
(15)
16

---

Published as a conference paper at ICLR 2021
where è is some nonzero real number.
Let us now take a closer look at the vector " the limit direction of X r. Recall from Section 2.1 that for any E [n].
[r]: = y exp(-y/Jioca 1c)) - exp(- 3ro (Ot)),
case of classification. Recall that ()oro() - oo while converging to certain direction Bio pe). This means that if
y 2 (1c( > y (Ox
for any i,j E [n], then
lim exp(-yyæ BIG 1 (t)))
0.
(16)
10000 exp(-y;:: Bic ② io (())
Take to be the index of any support vector, i.e., any that attains the minimum yau fic ( among all data points. Using such an i, the observation (16) implies that lim (r))]p = 0 for any
zy that not a support vector. Thus, by the argument above, u 0 can in fact be written as
Ei (r((()
u
lim t0000
(17)
i= D. (r(r)l))
where 2 0 for all i E [n], and My = 0 for xtys 's that are not support vectors. Combining (17) and (15),
B O
(18)
Recall that we do not yet know whether introduced in (15), is positive negative; we will now show that e has to negative, From Lyu & (2020), we know that (()r.(t)) + 0, which implies that af Bi ()))) > 0 for all i E [n.]. However, if c > 0, then (18) implies that Big (O%) is inside a cone K defined as
K
Bua 1/ s O, Vi E [m]
Note that the polar cone of KC, denoted as KC is
1C (= | S 0, K.} (z y = 2 0, V [n]].
known that ic 10 = {0} for any convex cone K. and its polar cone K Therefore, having implies that ( E K. K2, which means that there exists some E [n] such that y (to( < O; this contradicts the fact that the loss goes zero + oc. Therefore, in (15) and (18) must be negative:
Bic O x
Paya;
(19)
for v 2 0 for all E [m]] and v = 0 for all v; that are not suport vectors.
Finally, compare (19) with the KKT conditions of the following optimization problem:
minimize
||=1|²
subject to n 2 2 1, Vi [n].
The KKT conditions of this problem
= P.ye, and 2 0, 14 y 2) = 0 for all i [n),
where M......, An are the dual variables. Note that this is (up to scaling) satisfied by Bie (0 (19), we replace μ 's with 24 ss. This finishes the proof that 3 (0 is aligned with the lg max max-margin classifier.
17

---

Published as a conference paper at ICLR 2021
D PROOFS OF THEOREM 2 AND COROLLARIES 2 & 3
D.1 PROOF OF THEOREM 2
D.1.1 CONVERGENCE LOSS TO ZERO
Since Theorem does not assume the existence of lo 2 satisfying (()) 1, we need first show that given the conditions on initialization, the training loss (()(t)) converges to zero. Recall from Section 2.1 that
V. (()) (-XXrr) (0 (V...... 11 I, 041::.... Ut)-
Applying the structure (9) in Assumption 1, we get
òj M(-X T r) o (V), 11 1, Aa 04+1...., U2)
m SX r1 (U)). ... (00r))_,....0._lUU-- of (U]), of (1 ... Uz)
/=1
m
>
[SSx),, rly
[ Uil
j=1
kilf
Left-multiplying U.² (the conjugate transpose of U() to both sides, we get
U = - -
Uf Uk
(20)
where II
denotes the product using entry-wise multiplication C.
Now consider the rate of growth for the absolute value squared of the j-th component of U/ vn
xi |UT v1ll J 10? onl, UT m1 di LUT wll
O m)y + [U," b (T mij
2R (o btl UF mils)
22 (-ISXT r/s II UK ouls
UJ on for any 1' E [L]. di
so for any j [m]) the squared absolute value of the j-th components in UP" oi grow the same rate for each layer 1 E [Z]. This means that the gap between any two different layers stays constant for all 2 Combining this with our conditions on initial directions, we have
[[U] (t)l, I (0)))
!!U| v, (0), {0)
(21)
= a² = - a²
2a2,
for any j E [m], / E [L - 1), and 2 0. This inequality also implies
||, (0),2 2 [[TTe + + 22
(22)
Let us now consider the time derivative of C(O(t)). We have the following chain of upper bounds on the time derivative:
d di
((e())==<((0())
V ((
< - --IVv, = - (111
(0)
oz (6) Sx r(t) O I
vF
KLL
---", SXX (()) L
| (t),,
18

---

Published as a conference paper at ICLR 2021
(9)
- -a 21 21 1-1 Σ |SX r(t)),
a 21-22 21- 1 r(t)ll
2 22 2L 1- mmin S) 3121""r(11)
(23)
where (a) used the fact that |1 (1)13 U (1)l because it is a projection onto subspace,
and || UL vz. (f)1l2 = | oz (1)l because UH I : (b) is due to (20); (c) is due to (22); and (d) used the fact that S E C is matrix that has full column rank, so for any 2 E C we can use || 112 2 Smin (S)[=11l where smin (S) the minimum singular value of S.
We now prove lower bound on the quantity ||_x" rt)) Recall from Section 2.1 the definition of [r(t)]+ = -y -: (a,; (t))) for classification problems. Also, recall the assumption that the dataset is linearly separable, which means that there exists a unit vector z E Rd such that
y: 2 0
holds for all E [n]] for some 7 > 0. Using these,
| rt)l
y exp( - y: (2,; (
y: exp( exp(- y/ (x,; 0())))
Combining this with (23), we get
d
(()))) S 2- 8min 5m)n(5))+((((1))
which implies d
((O(t)) S (()()))
+ 22 s smiul (5)222t
Therefore, ((E(t)) - as cc.
D.1.2 CHARACTERIZING THE LIMIT DIRECTION
Since we proved that (()())) + 0, the argument in the proof of Theorem 1 applies to this case, and shows that the parameters 8y converge in direction and align with ú V., C(O). Let es"
lim
mi(t) be the limit direction of vz. (x)(2
The remaining steps of the proof are as follows. We first prove that SX rt) converges in direc- tion x Using this u we derive number of conditions that has to be satisfied by the limit directions the parameters. Finally, we compare these conditions with the KKT conditions of the minimization problem, and finish the proof.
By Assumption 1, we have
m
L U vily
f(x: θ) ((z) (UI...., ... = Σ
Sx II
j=1
[-1
m Σ
Iuu mily [A]
ST
[Iear
Ułun
x ST
Here, we defined p == Ne U. v. E Cm. Since the linear coefficients must be real, we have S IRd for any real vr's. Since vi's 's converge in direction, also converges in direction, to p p==== [[e[ UT up So express the limit direction of (()) as
8(0)) x ST II [Ieeu
UT = ST ~
(24)
19

---

Published as a conference paper at ICLR 2021
From (20) and alignment of ia and ét we have
lim UP (1( lim (Uf mn)))) t-000
lim SX r()) t-000
Il
kigt Ug vx(().
(25)
t-
kig
Since all vectors U/ (t) converge in direction, the term S (t)) should also converge in direc- sx*r(t)
tion. Let u == lim r|s One can use the same argument as in Appendix C.2, more specifically (16) and (17), to show that u can be written as
S SE [.((())e x. (r(0]]l2
u ~
lim
(26)
S
where v4 2 for all E [n]. and by for æj that are not support vectors, i.c., those satisfying Moay S p min4e]o] ya s p
Using " we can rewrite (25) as
0f x ~0 3 II kil
for all E [L]. Element- wise multiplying U. op to both sides gives
of o U.! = of
02 & - ① Il
RELL oh = 2 ④ p
(27)
where a 0h denotes element-wise b-th power of the vector a. Since the LHS of (27) is a positive real number, we have
arg([[U? m1ls 12) = arg([- u mi) + arg([p>))),
(28)
so using this, (27) becomes
UP o 101302
12 x 0 @ 1
(29)
Now element-wise multiply (29) for all E [L], then we get
100002 |u p 1o
(30)
close look at (30) reveals that if T, 2 2, ~ and u must satisfy that
1,| + 0
1 ||p 1| -
(31)
for all j E [m]. There is another condition that has to be satisfied when L = 2:
|| 0, 11p0 b #0 0 , S 1|u 1,rl
(32)
for any J.j E [m]; let us prove why. First, consider the time derivative of [p]; = UUToi vzlj-
d dt [p(0], = UT vi (1), d
v2 - o2 d (1],
di
-SXx r (00
(33)
where (a) used (20). Now consider
de (ptt) r ( [
[SX TfT (1), o0
(34)
|SXTr(t)l2
[p(t),
We want to compare this quantity for different j. E [m]. Before we do that, we take a look at the last term in the RHS of (34). Recall from (21) that
[U v. (t))
o0(),) | (0)),) 10 02 (0))
(35)
For simplicity, let 8, == [Uf 01 (0), | (0), which is a positive number due to our assumption initialization. Then, show that
(35) and [[((t)
v2(t)) to
|UT vi (1), + +
2 02 (() + 6,
2 2,
[[p()))
T v. (t)
U un (t),, +
20

---

Published as a conference paper at ICLR 2021
Of 11 = 2 if lim [02 v2(0) = 0o. [((())
lim 7-000
700
Recall that we want to prove that (32) should necessarily hold. For the sake of contradiction, suppose
that there exists j [m] that satisfies ||p011 [ 0 but [ [u
|[ for some j' [m]
satisfying I 01p111 I # O. Note that having [|p0]]] | = 0 and l l
* 0 implies that [|((t)l= + co
and ||(())1] [[(()),
We now want to compare the ratio of (34) for j and j'. First, note that
[SX" (())))(())XX"'///// r(0lz
1/x00)
SX (x)r(t)) 1/ lim
> 1.
(36)
|
Next, using 5 > 0, we have
[pttll [[(()p]
and the fact that
+
26 is decreasing function of æ 2 for any xV24+3
OU 0n + U3 02 (1), (1),P))))(()))))))) N ( 01 (t), + UU (t)l P)) ([]
(37)
for any t to. when to large enough. Combining (36) and (37) to compare the ratio of (34) for and j', we get that there exists some to 2 0 such that for any t 2 to we have
p(())) [P(OL] (t) [p(t)),1
> 1.
(38)
This implies that the ratio of the absolute value of time derivative of [p(t), the absolute value of current value of [p(()]; is strictly bigger than that of [p(()],- Moreover, we saw in (33) that the phase of Ze [p(()]; converges that of I[u Since this holds for all & 2 ty (38) results in growth of [p(t)], that is exponentially faster than that of [p(t)] so [p(t)], becomes dominant
component in pt)) as t + co. This contradicts that [p 0, hence the condition (32) has to be satisfied.
So far, we have characterized a number of conditions (26). (28), (31), (32) that have to be satisfied by the limit directions n and p of X and p. We now consider the following optimization problem and prove that these conditions are in fact the KKT conditions of the optimization problem. Consider
minimize PE
||Pll/\
subject to
yats p 2 Vi [n].
(39)
The KKT conditions of this problem are
@l1el12/2 3 S Σ payke and p4 2 O, 14(1 - y ST p) = 0 for all E [n].
where Mı,..., Mn are the dual variables. The symbol Ô |1-112/z denotes the (local) subdifferential of the L norm', which can be written as
|| pll: = {u E Cm ||[4]|| & for all j e [m]. and [pl, + = [u), = =exp(V-Larg(())))
(in this case ² ||||, is the global subdifferential), and
0 01ell1/1.
C [p]; 40 [u]; = eex(V=
if L > 2. By replacing J. 's with v4's defined in (26), that p and u satisfy the KKT conditions up to scaling. Therefore, by (24), (t)) converges in direction aligned with ST p where ~a6 is again aligned with stationary point (global minimum in case L = 2) of the optimization problem (39).
check from (26), (28), (31), (32) that the
If S is invertible, gives the last statement of the theorem.
get S - (-)))( pa. Plugging this into the optimization problem (39)
the definition of subdifferentials used here is taken from Gunasekar al. (2018h).
21

---

Published as a conference paper at ICLR 2021
D.2 PROOF OF COROLLARY
It suffices to prove that linear diagonal networks satisfy Assumption 1, with S = Ia. The proof very straightforward. since (a) IRdx- has (f) remaining entries are zero. It is straightforward to verify that M Maiag (2) satisfies Assumption 1 with
[ while all the
S U1 UL
Ia. direct substitution into Theorem gives the corollary.
D.3 PROOF OF COROLLARY
For full-length convolutional networks (ki = ... = kL = d), we will prove that they satisfy Assumption 1 with S d d F and U1
UL F*, where F Cd is the matrix of discrete Fourier transform basis [Fl,.: Vd exp( --I--mli-Diik- and F is the complex conjugate of F.
1
For simplicity of notation, define dh exp( v With such matrices S and U1,..., UL. can write M (x) as
((x) =
Sx و ((U1) @ (U21.3 @ (L)-s)
5=1
v//va --G--1/Va /Va sp 1--00-1//V2
(D)(--)))((
j=1
(d-1)-)6--1)) /d
where a @T. denotes the L-times tensor product of a. We will show that M(x) Mcony (x). For any j1.... , ju [d].
M( M
1
(1
e 1-
d
1=1
d
[x]
(1(
5g 1--
d
Recall that
d (1) 10
if - 1o + is a multiple of d, d
0
otherwise.
Using this, we have
MM [M(x))amndd
Σ
x
Σ
(1- 111- 1.+1)
[2
Σト Ju L+1 mod
MMonn (2: (a))ii....
Hence, linear full-length convolutional networks satisfy Assumption with S = d - F. A direct substitution into Theorem and then using the fact that |> | for any real vector d gives the corollary.
E PROOFS OF THEOREM 3 AND COROLLARY 4
E. PROOF OF THEOREM 3
E. CONVERGENCE OF LOSS ZERO
Since Theorem does not assume the existence of tn 2 satisfying L(O(tt)) < 1, we need to first show that given the conditions initialization, the training loss L(O(() converges zero. Since
22

---

Published as a conference paper at ICLR 2021
L 2 and M(x) U1 d write the gradient flow dynamics from Section 2.1
ò1 -M r) (Ihy v2) = - d U2.
(40)
02 M(XTr) (V1, Ika) -rU2 diag( U v1,
where r(t) y exp( (z (t))) is the residual of the data point (a, v). From (40) we get
Uf 01 -s U2 02, U 02 -s Uf v2.
(41)
Now consider the rate of growth for the j-th component of U/ U1 squared:
d UT 111 2|U7 1, Uf bn1 -2 -2rrs) 11 U2 02l,
d
dt U22 02
(42)
dt
So for any j E [m]. [UT 13 and [U] 02l3 grow at the same rate. This means that the gap between the two layers stays constant for all / 2 0. Combining this with our conditions on initial directions,
off vi(1) - IU2 02 (t)] |U} 0n (0)) - UU (2)
(43)
a UP 0113 a² 021 a²>,
for any j E [m]] and 2 0. This inequality implies
[UT (t)l 2 UU v2())) + a²x.
(44)
Let us now consider the time derivative of (()(()). We have the following chain of upper bounds on the time derivative:
d dt ((O(t)) = Vo = ( (V
< - [() - (+)l
(
1 (1)11 (6) -()) of
-r())) Σ ,n [0][UTo,101)
2 aa (r())) 1=1 |s]
m
-2 (/))=|)/((((t)))
where (a) used the fact that (1) and ||U2U' oz From this, we get
UU2U 02 (t) because it is a projection onto a subspace,
82(() because U2 Iazi (b) is due to (41); (c) is due to (44).
(()(0))
((0(1)) < 1+ a
Therefore, L(O(t)) - 0 as co.
E. CHARACTERIZING THE LIMIT DIRECTION
Since we proved that (()(t)) + 0, the argument in the proof of Theorem 1 applies to this case, and shows that the parameters vn converge in direction and align with é; = v., C(O). Let of :=
lim;-roc Uf (1) C U (1) and p UT of @ UT 6g
(t) (e)l be the limit direction of As done in the proof of Theorem 2, define p(t)
It follows from r(t) y exp(pv// (=; (t))) that we have sign(r(t)) sign(y). Using this, (41), and alignment of by and ú, we have
UT ys Uf U a of
(45)
Element-wise multiplying Uf of to both sides gives
(Uf of p (U
ys o
(46)
23

---

Published as a conference paper at ICLR 2021
Since the LHSs are positive and is positive, the following equations have to be satisfied for all j E [m]:
sign(y) (y) = lggn( Now, multiplying both sides of the two equations (46), we get
(47)
20 02 00 v x 002
(48)
From (48), pee must satisfy that
I + 0,
5' #0 - | = |[>]>=|
(49)
for all j.j E [m]. As in the proof of Theorem 2, there is another condition that has be satisfied:
I 0, 10 * #
| - ||
(50)
for any j.j [m]] let us prove why. First, consider the time derivative of [pl, ouT bu vzly
d U 1 (t),, - 1 u2 (t))), dt
dt [p(t)), = UT (t),
UT (t)l,
dt
(a) (( (t))))
where (a) used (41). Now consider
Hl(ttL] r (()))
UU vn (1)) + [[)]3
de
||ا]
(51)
[((()]]
We want to compare this quantity for different j. [m]. Before do that, take look the last term in the RHS of (51). Recall from (43) that
[U (t)) UU, v2(1)] + [UT 01 (0)} -U 02 (0)3.
(52)
For simplicity, let 6, := [UT vi (0)} -UT (0)}.. which is a positive number due to our assump- tion on initialization. Then, we can use (52) and [p(t)] = |UT (t), that
to show
IUT (1)3 + 1U o2(())
U U2 (t)) + +
2
[pt())
10 v U33 U2 (0) + +b
Uf vi (1)) + IUA v2)3
lim
if lim I (2)()) oc.
[p(())}
Recall that we want to prove that (50) should necessarily hold. For the sake of contradiction, suppose
that there exists j E [m] that satisfies [p = but [$},] > [[s] for some j' E [m] satisfying
[p f # 0. Note that having [0
and [p l'' # 0 implies that [[(()),;] + Do and
[o(t))al + 0. We now want to compare the ratio of (51) for j and j'. Using
[e()]] [(()))) + 0 and the
[((()),r1
fact that 26 is decreasing function of av/246
for any 8 > 0, we have
[ 02 12 (t 21,
(53)
(UT vn (1)3 o3
1) (10)
for any t 2. fo. when to is large enough. Combining πe
||اا|| > 1 and (53) to compare the ratio of (51)
for j and j', there exists some to 2 0 such that for any t 2 to. we have
- /P(0))///P(()) (POLL 1.
(54)
[p(())>) | [p())
This implics that the ratio of the absolute value of time derivative of [p(t)] to the absolute value of current value of p(t)], is strictly bigger than that of [p(t)]p. Moreover, by the definition of r(t), d (p(()), does not change sign over time. Since this holds for all 2 to. (54) results in growth of di
[[(())]p] that is exponentially faster than that of [(())) so [p(t)], becomes a dominant component
in p(t) co. This contradicts that [ = 0, hence the condition (50) has to be satisfied.
24

---

Published as a conference paper at ICLR 2021
So far, we have characterized some conditions (47), (49). (50) that have to be satisfied by the limit direction px of We now consider the following optimization problem and prove that these conditions are in fact the KKT conditions of the optimization problem. Consider
minimize PER
||e||
subject to ys" p 1.
(55)
The KKT condition of this problem is
i Plpl1 ys, where the global subdifferential @ ||-11, is defined as
a || {u R | s 1 for all j E [m]] and [p]s
[u]j sign((p),)}
We can check from (47), (49), (50) that the that pa satisfies the KKT condition up to scaling.
Now, how do characterize of and 2. in terms of pa Let ni UT of and mh U u Then, 0f = ~ U,U? of holds because any component orthogonal to the column space of U1 stays unchanged while the component in the column space of Uj diverges to infinity. By (42), |n
2 p 1010/ By (45), we have sign(nf)) sign(y) C sign(n
E.2
PROOF OF COROLLARY 4
The proof of Corollary boils down to characterizing the SVD of Meonv-(a))
E.2.1
THE l 1 CASE
First, it straightforward to check that for L = 2 and Lı 1, we have
Beonv ( conv) 122
For 1 = 1, the data tensor is simply (æ) = x². Thus, we have U1 = 1, U2 -
and ||/|||- Substituting U1 and U2 to the theorem gives the condition on initial directions in
Corollary 4. Also, the theorem implies us that the limit direction 2i of U2 satisfies vi x you
Using this, it is easy check that
Geonv + Dc
Donv)
x D. 02 x ya..
E.2.2 THE Kj 2 CASE
First, it straightforward check that for L and k 2, we have
U1
0
11
l2
[
[1
0
[
[mi]]
0
Boonv ( rcnn))=
V22
(56)
[v1]
0
[2122
[e1h]
For hi = 2, by definition, the data tensor is
M M (x:)
T T
and it straightforward to check that the SVD of this matrix
x.
1/v2
1/v2
v | + xx &o
0
v2
x +
Mcony (x) =
T T
=
1/V2
-1/V2
||
2 xr
in
xe
so
x 1 + T
1/v2
1/v2
=
U =
U2 =
1/V3
-1/V2
V2V x
|
x
25

---

Published as a conference paper at ICLR 2021
Substituting U1 and U2 to the theorem gives the conditions initial directions. Also, note that the maximum singular value depends on the sign of x"' E. Consider the optimization problem in the theorem statement:
subject to ys 2 1. If x > 0, then the solution pe to this problem is in the direction of [y 0). Therefore, the limit directions of and v2 will be of the form
minimizepeR*
llll
vi ci
2. c2(x +),
where sign(c1) sign(c2) sign(y) (y). Using (56), it is straightforward to check that
0
0
0
0
0
0
0
Beony O conv y
(xc +
y (2x:
E + ).)
:
0
1 1
Similarly, if T0 < O, then the solution p is in the direction of [0 y]. Using (56), we have
1
0
-1
0
0
-1
0
Beonv 4 00
y
(x x = y(2x E - x).
-1 1
F PROOFS OF THEOREM 5, COROLLARIES 5, 6 & 7, AND LEMMA 4
F.1 PROOF OF LEMMA 4
In this subsection, restate Lemma 4 and prove it.
Lemma 4. Consider the system of ODEs, where p,q: - R:
p=p p= 9g n p=p²-1, p(0) = 1, (0) =
Then, the solutions (t) and (t) are continuous on their maximal interval of existence of the form (-c,c) C R for some (0, oo). Define hy,(t) (1) (l); then, hr(l) is odd and strictly increasing, satisfying limere (t) co and lim,,-c (1) -0.
Proof First, continuity (and also continuous differentiabilltt)) of p(t) and q(t) is straightforward because the RHSs of the ODEs are differentiable in and q. Next, define jit) p(-t) and g(t) = -q(-t). Then, one can show that 5 and q are also the solution of the ODE because
de 5(1) dt p( -1) --((-() = - -()))
d
dt g(t) dt ((-))) = q( d(-t) = pl -(- -1 p(t)
However, by the Picard-Lindelae theorem, the solution has to be unique; this means that p(t) = p(t) = p(-1) and qt) 7(() = - q( ()), which proves that p even and q is odd and also implies that the domain of p and g has to be of the form (-c, c) (i.e. symmetric around the origin) and q is odd.
To show that h is strictly increasing, it suffices to show that p and q are both strictly increasing on [0, c). To this end, we show that p(t) 2 1 for all t E [0, c). First, due to the initial condition p(0) = and continuity of p. there exists é1 > such that p(t)
0 for all t E (0) that q(t) p(t) -1 > 0 for E I \ {0). so g is strictly increasing on IT- Since g(0) = O, we Therefore, is
I₁- This implies
have q()) > 0 for E J \ (0), which then implies that p(t) p(1)--2q(1)
26

---

Published as a conference paper at ICLR 2021
also strictly increasing on I1; this then means p(t) 2 1 for t [0, because p(0) 1. Now, due
to p(e1) 2 1 and continuity of p, there exists 62 > <1 such that p(t) > 0 for all t E [e1. 62) =: 1z-
Using the argument above for Ig results in p(t) 2 for t E [0, E2). Repeating this until the end of
the domain, we can show that p(t) 2 holds for all / E [0,c) c). By p 2 1, we have q = p²-1 2
on (0, c), q is strictly increasing on (0, Also, q(t) >
(0, c), so pb-2q q
on (0, c)
and is also strictly increasing on [0, c). This proves that h is strictly increasing on [0, c). and also on (-c, c) by oddity of h.
Finally, it is left to show limete h(t) - oo and himes-eh()) - -c. If c < co, then this together with monotonicity implies that the limits hold. To see why, suppose Then, and can be extended beyond 2 which contradicts the fact that (-c, c) is the maximal interval of existence of the solution. Next, consider the case c co. From p(t) 2 1, we have ((t) 2 1 for 1 2 O. This implies that (()) 2 for t 2 O. Now, p(() 2 p()) (t) 2 t, which gives
oo and limete h(t) < co.
p(t) N g2 + fort 2 Therefore, we have
t
4-1
lim h(t) lim p(t)==1q(1) q(t) 2 lim 8+00
= +
t= 00,
1-000
1000
2
hence finishing the proof.
F.2 PROOF OF THEOREMS 5
F.2.1 CONVERGENCE OF LOSS TO ZERO
We first show that given the conditions on initialization, the training loss (()(()) converges to zero Recall from Section 2.1 that
i = V. ((O) = ((X"rr) o (oi,..., 01 Iky 0441..., u,))
Applying the structure (9) in Assumption 1, we get
ùن M(-X" r) o (UI,.....
Inp Ut41 U2)
m
- sx" rl,(0/ of 8 1141 ... -
1=1
- ---isxTm [Sx"r) r]
II [U
j=1
Left-multiplingg U." to both sides, we get
U
o II
T
Ut
Us.
(57)
ligh
where I denotes the product using entry-wise multiplication C.
Now consider the rate of growth for the second power of the j-th component of U. mi:
d L I 01 2 on UI vil; -2SXX" r) II - [K oul,
d | vrls
dt
for any 1' [L]. Thus, for any E [m)] the second power of the j-th components in U. grow at the same rate for each layer E [Z]. This means that the gap between any two different layers stays constant for all t 2 O. Combining this with our conditions on initial directions, we have
UUT v. (1)3 [U v1]3 [U] v (0)) vI a [m] 2 a²x,
on
for any j E [m], 1 [T. - 1), and 1 2 0. This inequality also implies
[U] (1]3 2 [UE o0)) + +
(58)
27

---

Published as a conference paper at ICLR 2021
Let us now consider the time derivative of (()(t)). We have the following chain of upper bounds on the time derivative:
dt = - (
$ -[ = - 11
1 - sx (4) ④ LyL
Uh v1))
Σ, SSX r(t)]} II UK o2)1
2 aa 2 26-2
(x'r((1)3
26-22 2 1 r(t)l
② 26 22 miaa (5) smin (X) (
-22 22 2 min (5)² min X (t))
(59)
where (a) used the fact that |1 (1) 2 | (1) because it is a projection onto subspace, (t)l because U I (b) is due to (57): (c) is due to (58); and U dz (t)ll = (t)]
and (d) used the fact that S E _mxd and X E Rd are matrices that have full column rank, for (x)] ||21||2 where smiu(} (-) denotes the minimum
any 2 E C", we can use ||SX 2112 2 Smin ( sminn (X)
singular value of matrix.
From (59), we get
(()( - exx smin (S)) (x)
(60)
so that (()(t)) 0 as
F.2.2 CHARACTERIZING THE LIMIT POINT
Now, we move on to characterize the limit points of the gradient flow. First, by defining a "trans- formed" version of the parameters (1) == U. (t) and using (57), one can define an equivalent
system of ODEs:
i = SXX r ④ II k
nh for 1 E [L]]
(61)
(( = an for I [L [L- 1]. n (0) 0.
Using Lemma 4, it is straightforward to verify that the solution to (61) has the following form. For odd L,, we have
(t()) a.7) pr. (-a" ( SX (((()drr) for E [L-1]] 1].
(62)
1 SXT [ ((())rr)
(t) a/ri g1
Similarly, for even L, the solution for (61) satisfies
-at-2 2 Sx" ( ((r)))) for E [L-1] 1),
(t) = am 3 PL
(63)
-a1-22 SX" S r(r)dr):
(t()) an qu
Now that we know how the solutions n look like, let us see how these relate to the linear coefficients of the network. By Assumption 1, we have
f(x; ) M(x) (v ..... v2)
D
[Sx
II uf vzl
j=1
28

---

Published as a conference paper at ICLR 2021
Σ
[mmb
[5] x S²'S"'
(I m = x." ST
1=1
Here, we defined p [ written as (()())) S p(t). From the solutions (62) and (63), we can write
R Therefore, the linear coefficients of the network can be
((() II (1) - a" m oz o hr (-a"-217100 1 o oxx" (((t)at).
L
==1
where 1ı = p qL, defined Lemma By the convergence of the loss to zero (60), we have lim;- X xx((((1)) y. Therefore.
xSt
(19 2 oh 1- oL SX
I-- ((())dt)) y.
(64)
Next, we will show that p is fact the solution the following optimization problem
minimize PER"
QLa.((p)
subject to
XST y,
(65)
where Quaa. R + R is norm-like function defined using HI.(1) = So 1 (T)
m
[p|;
QLan(()) = a²
m H
az [
1=1
Note that the KKT conditions for (65) are
XS" p y, V vpLLa.(()) SX
for some RR,, is clear from (64) that pa satisfies the first condition (primal feasibility), so let us check the other one. Through straightforward calculation, get
V vplLan(() 2- 02-L @ h (a-1m -(-)))))
Equating this with SX" gives
b |n| 02-1 o nT: (a -1-1 00 ((-1))))))))))))))))))))))))))))
op) SSX
1 (a n7 0(- U p) = 1. 17 01-2 Sx
+ p = a" n' ob o h2 (a' O v)
Hence, by setting le dT, p satisfies this condition as well. Also, if S is invertible, can substitute p = T (65) to get the last statement of the theorem. This finishes the proof.
F.3 PROOF OF COROLLARY
The proof is direct consequence of the fact that Assumption holds with S U, UL Ia for linear diagonal networks. Hence, the proof is the same as Corollary 2, proved in Appendix D.2.
F.4 PROOF OF COROLLARY
We start by showing the DFT of real and even vector is also real and even. Suppose that Rd real and even. First,
(_V-T.
2T(j 1)(k - 1)
Fx); = Va
Σ Jol exp
29

---

Published as a conference paper at ICLR 2021
2T(j 1)(k -
d
2T( 1) 1)
[ell cos
[ sin
d
d
k=1
2T - 1)(k-1)) - 11 11 R
[x3]x j. cos
for all j [d]. To prove that Fæ is even, for j = 0, O.......
d=3
we have
2 1)(k--1)
Fa
ac 0o8
Vd
d
1
2T -1) 2n + 1)(k: -1
a cos
vd
k=
2n((d= -j j -1)(k: -1
c a cos
Vd
d
2n - j- 1 1)
[cc cos
vd
F Fxldsss.
proved in Appendix D.3 that linear full-length convolutional networks (k) ky d) satisfy Assumption with S d F and U1 = ... = UL = F", where F E Cdxd is the matrix of discrete Fourier transform basis [F] Va exp( 1-11- and F* is the complex conjugate of F.
The proof of convergence of loss to zero in Appendix F.2.1 is written for real matrices S, LU,,...,ü, but we can actually apply the same argument as in Appendix D.1.1 and prove that the loss converges to zero, even in the case where S, U....... UL are complex.
Next, since Uj's are complex, we can write the system of ODE as (see (20) for its derivation)
= =
FX O
(66)
Since all data points æ; and initialization wi (0) are real and even, we have that FX r is real and even, and F* ("'w(() (w)( are real and even. By (66), are also real and even. Thus, the parameters wt) are all real and even for all t 2 O. From this observation, we can define m!() == Fw, (t), == Fw, and S = ==' Re( which are all real by the even symmetry. Then, starting from (61), the proof goes through.
that the time derivatives of Fw!
F.5 PROOF OF COROLLARY
Since the sensor matrices A A...... .A. commute, they are simultancously diagonalizable with a real unitary matrix U E Raxd i.e., UT A,U's are diagonal matrices. From the deep matrix sensing problem (13), we can compute V Ww,fms which gives the gradient flow dynamics of W.
Wi Ww,44 Lms W
WT "
r, W
where r; = (A,, W and right-multiply U to both sides, get
... Wi) - yı is the residual for the i-th sensor matrix. If we left-multiply UT
U U'WU -UT U W W
T.U A.U W UJ W.WLLU (67)
If TH W U is a diagonal matrix for all + I, then U W: is also a diagonal matrix. Note also that, since Wi = al, = aUUT for I E [L - 1], the product U W,U is a diagonal matrix at initialization. These observations imply that Wi(l''s are all diagonalizable with U for all i 0.
30

---

Published as a conference paper at ICLR 2021
Now, define (t) eig( Wi(t)), ie., U'U diag(vr). Also, let æ, cig(A.). Then, (67) can be written as
أ =
vk.
Therefore, this equivalent to the regression problem with linear diagonal networks, initialized at vr( al for I E [ -- 1] and nn (0) = O. Given this equivalence, Corollary 7 can be implied from Corollary
G PROOF OF THEOREM 6
G.1 CONVERGENCE OF LOSS TO ZERO
We first show that given the conditions on initialization, the training loss (()(() converges to zero. Since and M(x) = U1 diag(8 U) we can write the gradient flow dynamics from Section 2.1
d M(X r) (Ihr U2) = -U, diag( $ s) U2
(68)
8² M(x T r) (V1, Ik2) = -rU2 diag diag(s)U{ v1
where r(()= = (a:; (1)) - y is the residual of the data point (xc v). From (68) we get
Uf é. - r8 o U2 02, U 02 = -r v.
(69)
Now consider the rate of growth for the j-th component of UT un squared:
_
[Tu = VIT UTo,
d 2r] 0 U vel, = di FUTTo 02l3
So for any j E [m]. [UT 13 and UVZ v2l3 grow at the same rate. This means that the gap between the two layers stays constant for all N 0. Combining this with our conditions initial directions,
of - IU (0)3 = IUT o0) v2 a a 1113 a² 22 0213 a²x,
for any j E [m]] and 2 0. This inequality implies
[0 (t)) 2 UU v2(1))3 +
(70)
Let us now consider the time derivative of C()(()). We have the following chain of upper bounds on the time derivative:
d dt =(0())= (e(()))))(( - (
-- 22
(2) < - 12) -- -1)) o o
= - Σ 10]
2 a² (t) 1s
= 2 ((((t)))(((t)
where (a) used the fact that (t) UUU (t) because it is a projection onto a subspace,
and ||UgU? öz (t)ll |0 (t) because U2 INy (b) is due to (69); (c) is due to (70). From this, we get
(()()) < (() expl- 2a 20|2||
(71)
Therefore, ((O(() 0 co.
31

---

Published as a conference paper at ICLR 2021
G.2 CHARACTERIZING THE LIMIT POINT
Now, we move on to characterize the limit points of the gradient flow. First, note that any changes made in ii over time are in the subspace spanned by the columns of Uz. Therefore, any component in the initialization (0) ariy that is orthogonal to the column space of Uj stays constant.
So, we can focus on the evolution of vi in the column space of Uú; this can be done by defining a "transformed" version of the parameters (i(t) == U vi(() and using (69), one can define an equivalent system of ODEs:
" -88 ④ 722 1/2 -8 ④ 1/1 771 (0) - an? (0) = oft2
(72)
where 7i following form.
o1 7/2
U2 02. It is straightforward verify that the solution (72) has the
(tt)= amh O cosh
r(()dr)
+amp ② sinh
Jo r(r)dr)
o
(73)
{ r(r)dr)
+ anl @ cosh -8 { r(r)dr
(2(1) = onn O sinh
By the convergence of the loss to zero (71), we have lim f(x; ((t)) = y. Note that f(x; O(t)
can be written
f(x: ((t)) = ((x) (t), o2(t)) = ( ((z)uu())
vi (t) U1 U; diag(s)U = (n nz)))).
Therefore,
lim f(; (t)) lim 11000
s" (m n2(())
r(r)dr) o sinh (-s (-s/ L 0o r(F)dr)
a²sT
02 (7)
72 o cosh
(-8/ l r(F)dr)
sinh (-8 Loa r(T)dr))
+ (f)
O 72))
cosh
0 8
12
@ sinh
28 r(())d) (m 2 mp) o cosh
28 / r(r)dr)
2
[m])
[
2
>>
[s]
sinh (2(sl,p) + [m (7lyy cosh (2(si,u)
2
j=l
y,,
(74)
where we defined v - S r(T) dr) Consider function v + asiinl(()) + bcosh((). This is strictly increasing function if 16). Note also that
m
[ma]
| mall
(75)
which holds with equality if and only if [ = [ However, recall from our assumptions on initialization that [m]]] [m21]
0, (75) can only hold with striet inequality. Therefore,
[7 13
[
g(v) = Σ
ss
sinh sinh(2(s))z) + [ cosh(2(s))u)
2
1=1
a strictly increasing (hence invertible) function because it is sum of m strictly increasing func- tion. Using this g(v), (74) can be written as a² ggv)) = and by using the inverse of g. we have
/
V= ==
r(T r(T) --
(76)
a²
32

---

Published as a conference paper at ICLR 2021
Plugging (76) into (73), get
lim vn (t) t-100
U1 lim 7h (t) a(Ix: -U;U)) (1000
=aU1 i o cosh (0-1(2)) a² 8) n2 2 sinh (1-1 az) 8)) + a U,u
sinh
lim v2(() (-000
= U2 lim (2(()) + alIn - -U2U2 002 t-400
=022 t @ sinh (0
8) + 72 3 cosh (1-1 (z) 8) 8)) + aa(T2e YU2?
This finishes the proof.
H PROOF OF THEOREM 7
H.1 CONVERGENCE OF LOSS TO ZERO
We first show that given the conditions on initialization, the training loss L(O(I)) converges to zero. Recall from (10) that the linear fully-connected network can be written as
(ie( Oc) W' W₂ WT.11W1.
From the definition of the training loss L, is straightforward to check that the gradient flow dy- namics read
W; = Ww, (() = W W x
Wi for E [L - 1/,
W = Vw, ((Orc) = W x'''r,
(77)
(0 = WW for E [L-1], 1],
(0) LtW
where r R" the residual vector satisfying [r], fie( Oie)
Vt. as defined in Section 2.1.
From (77), we have
x r W W W w x XW W. W W Wt+ WT (+1 W44
W7 W, = Wi+1 W WW
for any 1 E [L 2]. From this, we have
d
wT Wi
W44 W dt
dt
and thus
wi(t) Wi+ wi(0)) Wi(0) - (0) a2W W. WW.,W.
(78)
for any / E [L 2]. Similarly, we have
W1- (1) wr (1))w, (r. W (0) w. (0)
(79)
aa -WWT_, Wi.1- a.
Let consider the time derivative of (()) We have the following chain of upper bounds on the time derivative:
dt Ve.. (Va =
S s-IVw, ((( (t)) = - (t)
--IW7- W
(80)
33

---

Published as a conference paper at ICLR 2021
Note from (80) that if W WT is full-rank, its minimum singular value is positive, and one can bound
W W X r|12 min (W ... W x r122- rr-l2
(81)
We now prove that the matrix W ... W full-rank, and its minimum singular value is bounded from below by a "-1 (//21//2 for any 2 0. To show this, it suffices to show that
W W Wi- ... WW..-Wi-L 2 Is.
(82)
Now,
WI-1 W. W.WWWiW WE-1
W W (W2 WW +a W W1 a W2W W.-..WL-11
W W. W. W W. W: WL-1
WI-1 WWWW + +a W. W2 - WWw-aave W WL-1
WT_ W (W, W W:
WI-1
= (W W, 1-
where equalities marked in (a) used (78), and inequalities marked in (b) used the initialization ditions W Wi 2 W4+1 W Next, it follows from (79) that
(W W--- 1-1 (MTM) a WT- WL-1 - 21 (WI WL-1 - w.w())"-
(0)
2
where (c) used the assumption that WT_, Wr.-1 w wf 2 Ala. This proves (82). Applying (82) to (80) then gives
((0)((1) S W W x" r11
S min (W ... W w 1
5 2t-2 1 X r 1
(4)
S 22 -1 min (x) (x) 1|
26-2 Omin X x (((cet(
where (d) used the fact that T is a full column rank matrix to apply bound similar to (81). From this, we get
((Orc(t) S (()).()) 2 I min (x),), hence proving (()re(t)) 0 as co.
H.2 CHARACTERIZING THE LIMIT POINT: a 0 CASE
Now, we move on to characterize the limit points of the gradient flow, for the "active regime" case - This part of the proof motivated from the analysis in Ji & Telgarsky (2019a).
Let un and be the top left and right singular vectors of W.. for 1 E [L 1]. Note that since W. varies over time, the singular vectors and singular value also vary over time. Similarly, let sj be the largest singular value of W,. We will show that the linear coefficients 3r. (Ote) W W wr align with ui as a + O, and u, is in the subspace row X) in the limit a - 0, hence proving that Bie (Oee is the minimum & norm solution in the limit 0.
First, note from (78) and (79) that if we take trace of both sides, we get
Wil I
W 1l
a²
W14 | for I [T 2].
34

---

Published as a conference paper at ICLR 2021
W 1 | a² (|| 11/2 1|
Summing the equations above for 1, + 1, ,...., , L - 1, we get W | = a² ( (ج0
(83)
Next, consider the operator norms (i.e., the maximum singular values), denoted as I1-11g. of the matrices.
Will 2 u/41 W W7ll41
U W W WT, 414 + a² f (W, W, W4+1 W
|W1+1l12 + a (W, Wi Wi+1 W 2u++
|W a Wi Wi+1 W/ill for E [L - 2].
W
WL
W WL-1
wt
|
wr.112
WL
T WL
+ aa²
WL
(
W
WL
|
|1ll|2
|22/12
1 a
WT-1 w, w ll2.
where (e) used (78) and (f) used (79). Summing the inequalities gives
W 2 2 |1 a
W WR - W&+1W2 122
(84)
From (83) and (84), we get bound on the gap between the second powers of the Frobenius norm (or the & norm of singular values) and operator norm (or the maximum singular value 81) of W::
W1O0 IW1O & a² a² w/ll (
+
W We WK+1 W ll,,
(85)
which holds for any 2 The gap (85) implies that each Wi, for I [T. - 1]. can be written as (i(t) = iı (t) (t)r)((((a))" Oaa)).
(86)
Next, we show that the "adjacent" singular vectors oy and tt4 align with each other as a + To this end, we will get lower and upper bounds for quantity u. WW++i W
of WT W o - of WT Win: a² W Wio, + a W4+ W 1+1 1i
2 2| a² W W, - WT+1 11
oी - a² W W: W Wi+iW/.ll,
(87)
o. Wi+1 1 (5{ u 1/41 + Wi+1 W+ttWT - 2 u/ T u(f1)
2 (o) )+1))² 2- + o/' (W WT [41 - u 1 1
54 (of u+ )² | | 112-
(88)
Combining (87), (88), and (85), we get
$t s/ (of 22 2 2 W W. < s (o) 2 + a²( W - 10 12) + +
W41 WT W 112 + W 1 Wi+1
4-1
W We W i.
(89)
k=1
Next, by a similar reasoning as (87), we have
N u W W i - a² W W W.W.
W44 W
(90)
Combining (89) and (90) and dividing both sides by 8i get
(vi(t) (())))=))(())² 1- 1 a G
(91)
314 (t)
35

---

Published as a conference paper at ICLR 2021
fort 2 where
G W (|W - 110b1112 +
W41 W
W W
- Wk+1 W We
By similar argument, also get
(vL- (t)
G5-1
a²
(92)
[t)(1)]1
where
GL-1:=2 - u.
From (91) and (92), we can note that as - 0, the inner product between the adjacent singular vectors converges to +1, unless 8 81-1 |/ also diminish to zero. So left show that the singular values do not diminish to zero a + 0. To this end, recall that we proved in the previous subsection that
lim XWi( WT- (z-1
necessary condition for this to hold is that
y lg X 2
L-1 II st(t) (w
- lim Wi(() ... WL-I(t)wL
lim 1-000
This means that after converging to the global minimum solution of the problem (i.e., - xc), the product of the singular values must be at least greater than some constant independent of a. Moreover, we can see from (87) and (90) that the gap between singular values squared of adjacent layers is bounded by O(a²), for all t 2 0; so the maximum singular values become closer and closer to each other diminishes. This implies that
1 1/L
1], lim lim [102( 1/11
1/L
lim lim (1)
for E [L. [L-1],
X
1/L
|X 11 1/L
Therefore, we have the alignment of singular vectors at convergence +
lim lim (vr(t)" (t))² =, for l E [L 2]. lim lim (1) (()"((()),,,(11))))) (1))
1. (93)
(t)l22
So far, we saw from (86) that Wi(t)'s become rank-1 matrices a + 0, and from (93) that the co and a + These imply that, as + oo and -> 0, Bio (e;)) is a scalar multiple of the un, the top left singular vector of W
top singular vectors align with each other
lim lim Bic (eee c. lim lim uy a-0
(94)
6000
for E R.
In light of (94), remains to take a close look at uu (t). Note from the gradient flow dynamics W1 that W, always a rank-1 matrix whose columns are in the row space X, since XTr E row(X) This implies that, if we decompose W, into two orthogonal components Wt and w!ll that the columns in W are in row(X) and the columns in W, are in the orthogonal subspace row (X) have
W = O, will = W,- That is, any component Wi (0) orthogonal to row X) remains unchanged for all / 2 0, while the component W changes by the gradient flow. Since we have
|--
W- S a Wille
the component in W, that orthogonal to row(X) diminishes to zero as a - 0. This means that the limit a - the columns of W1 are entirely from row(X), which also means that lim lim (e).)((()) row(X).
t-10
However, recall that there only one unique global minimum of Xx = y in row(X): namely, X (XX))-y the minimum & norm solution. This finishes the proof.
36


Reviews:
[{"review_id": "d2kMU7FaVCu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper first provides a general framework to represent fully-connected networks, convolutional networks, diagonal networks, etc., using tensors. For classification, with the exponential loss, linearly separable data and gradient flow, it is proved that the parameters of a linear tensor network converge to the singular vectors of the limiting data tensor. When the data tensor is orthogonally decomposable, which is true for linear diagonal networks and linear full-length convolutional networks, the function computed by the network is shown to converge in direction to a stationary point of the l_{2/L}-margin maximization problem, where L denotes the depth of the network. For underdetermined regression and the squared loss, this paper proves that gradient flow finds a global minimum which also minimizes a norm-like function. This paper further considers the special case where there is only one data point and two layers, and provides empirical support. \n\nI think the general framework which represents networks using tensors is interesting, and may be useful elsewhere. It is also nice to have a unified analysis of the implicit bias which also removes a few assumptions from prior results. \n\nOn the other hand, I think it would be better to include a thorough comparison between proof techniques used in this paper and in prior work. For example, Ji & Telgarsky (2020) prove that the weights and the gradients converge to the same direction, and Theorem 1 of this paper assumes that the weighted average of the data points by the residual vector r also converges in direction; the claim of Theorem 1 then almost already follows. What remains to be proved is that d|v_l|^2/dt is the same for all layer l, but similar results have appeared in (Arora et al., 2018), (Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced), etc. \n\nHere are some minor comments:\n1. For linear tensor networks, I think eq. (6) is actually a multi-linear form. I think it is worth pointing out and can help the readers.\n2. In the equation U_l^H U_l = I_{k_l} in Assumption 1, it seems that the dimensions don't match.\n3. It seems that the last sentence of Section 5.2 shouldn't be there.", "extra_scores": {}, "extra_text": {}}, {"review_id": "O1oJey8TPUS", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a tensor formulation as a unified framework for studying different architectures of neural networks. This formulation is mainly used under the special case of linear networks with “orthogonal” tensor representation to provide a unified proof of many existing results on the implicit bias of gradient descent under different architectures. Overall, the tensor formulation is an interesting and new (to my knowledge) abstraction. \n\nOn the other hand, in terms of writing, I found the key ideas behind the unified results regarding implicit bias to be a bit obscured within the tensor formulation. Since this paper is positioned as a new formulation with a goal of providing useful generalized abstraction, I believe it would be beneficial to be more explicit about the core ideas and their connections to existing concepts. In particular, have the following concrete suggestions:\n\n1. Although the tensor formulation is more general, introducing the results including the orthogonality condition for the case of L=2 layers first would be very useful. For 2 layers the analysis only requires matrix algebra and it is easy to motivate the generalization and identify the key unifying concepts. \n\n2. The condition on orthogonality of tensor formulation, which unifies existing results on diagonal and convolutional networks have an interesting connection to linear diagonal networks: I believe the condition is equivalent (in the sense of if and only if) to stating that there is exists *some* orthonormal transformation of the layer parameters v_l (v_l -> U_lv_l) and some linear transformation of input x (x->Sx), such that after the transformations, the networks behaves like a linear diagonal network. Thus, at the core, networks with orthogonal tensor representation are equivalent diagonal networks in a different parametrization. Moreover, from the proof, one can also show that this specific of change in parametrization does not affect the gradient flow path, i.e, that gradient flow on v_l is equivalent to gradient flow on the orthonormal linear transformation of the parameters tilde{v}_l=U_lv_l. It would be useful to discuss the connection between the orthogonality condition and diagonal networks explicitly in the text as a motivation/clarification for the orthogonality condition or as proof sketch. \n\n2b. Another connection is that, for L=2 where M(x) is a matrix, the orthogonality condition is also equivalent to commutativity of M(x_i) for the dataset inputs x_i -- this also highlights why for a single datapoint the analysis goes through as M(x) is a single matrix, which is commutative with itself. \n\n3. One of the main differences from the existing work is claimed to be the fact that this analysis does not make assumptions on convergence of loss. However, the main theorems introduce additional assumptions on initialization that effectively guarantee convergence of loss. It is not clear if this assumption is more useful than assuming the loss converges --  the assumption on initialization is more easy to control, however such constraints on initialization in turn affect the implicit bias explicitly. For e.g., in regression, the effect is explicit in the definition of Q, and for classification although the asymptotic direction is independent of initialization, recent work on diagonal networks show that the initialization has strong effects on the convergence to the asymptotic max margin solution (see https://arxiv.org/abs/2007.06738). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MpcoON5mTAF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper gives a general framework of what they call linear tensor networks, which is essentially linear neural networks that is expressed in the tensor formulation. Under certain assumptions, they show that the network parameters converge to the direction of singular vectors of the tensor. For linear fully-connected neural networks, they recovered prior result. For classification and underdetermined linear regression, they show under decomposable assumption the limit point of gradient flow and its characterization.  They further corroborate their results partly by a few very simple regression and classification task. \n\n* Strengths:\n\n1. The paper is organized in a way easy to read and follow. Given the amount of different pieces of results it has, it has a clear introduction section to explain the motivation and their contributions. The framework is written with examples of simple models. Within each piece of result when studying the limiting behavior of gradient flow, the assumptions required are stated clearly.\n\n2. The contribution of the paper, especially with respect to a number of related works, has been listed in a rather detailed and clear way in the paper. For instance for separable classification, the relationship with counterexamples for certain initializations in prior work; the comparison with prior results that only consider full-length filters etc. These comparisons and relationships can be found everywhere in the paper, and I think it meets the satisfactory criterion for a framework paper that aims at unifying and generalizing the prior understandings.\n\n3. The incremental contribution from prior work is valid. I think removing the convergence assumption for a number of prior works in characterizing the gradient flow and that generalizing the Woodworth et al.'s result for beyond the difference structure are both cool. While the setting that the paper has considered is still arguably over-simplified, I still view it as a nice step toward a better understanding for the implicit bias of the gradient flow for linear neural networks that offer nice insights.\n\n* weaknesses:\n\n1. To me some motivation and explanation behind the assumptions are lacking. Especially in Remark 1, if the initial direction is for guaranteeing convergence, then it might be more restrictive in use as compared with the convergence assumption, right? If not, some examples will be nice. Also, I believe it will be helpful to say a few words first on the assumptions of matrices, for theorems like Theorem 7.\n\n2. The classification experiments in Section 6 couldn't serve as corroboration for the theoretical results in the paper. Even though it is in align with some recent papers, it actually only shows the difference of limiting / finite-horizon behavior in dependence of the initial distribution. In that sense, I don't know how much it corroborates, or matters considering the points that this paper is making here. Also, the synthetic  dataset for the experiments seem a little bit too simple.\n\n3. Overall, I find this discussion on the problem's implicit bias, in terms of initial distribution for the 2-layer one data point case a bit confusing. It will be nice to state the motivation for considering this case, and also its implication for some for more general overparametrized setups.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper suggests an extension of previous implicit bias results on linear networks to a tensor formulation and arguably weakens some of the assumptions of previous works (e.g. loss going to zero is replaced with initialization assumptions). The reviewers were all positive about this work, saying it is clearly written and an original significant contribution. There were a few issues raised (e.g. the novelty of the proof techniques) and the authors responded. The reviewers did not clarify if this response satisfied these concerns, but did not change their positive scores. I will take this to indicate they still recommend acceptance.
Decision: Accept (Poster)