Year: 2021

Abstract:
The implicit bias induced by the training of neural networks has become a topic of rigorous study. In the limit of gradient flow and gradient descent with appropriate step size, it has been shown that when one trains a deep linear network with logistic or exponential loss on linearly separable data, the weights converge to rank-1 matrices. In this paper, we extend this theoretical result to the much wider class of nonlinear ReLU-activated feedforward networks containing fully-connected layers and skip connections. To the best of our knowledge, this is the first time a low-rank phenomenon is proven rigorously for these architectures, and it reflects empirical results in the literature. The proof relies on specific local training invariances, sometimes referred to as alignment, which we show to hold for a wide set of ReLU architectures. Our proof relies on a specific decomposition of the network into a multilinear function and another ReLU network whose weights are constant under a certain parameter directional convergence.

heading: 1 INTRODUCTION
text: Recently, great progress has been made in understanding the trajectory of gradient flow (GF) (Ji & Telgarsky, 2019; 2020; Lyu & Li, 2020), gradient descent (GD) (Ji & Telgarsky, 2019; Arora et al., 2018) and stochastic gradient descent (SGD) (Neyshabur et al., 2015; 2017) in the training of neural networks. While good theory has been developed for deep linear networks (Zhou & Liang, 2018; Arora et al., 2018), practical architectures such as ReLU fully-connected networks or ResNets are highly non-linear. This causes the underlying optimization problem (usually empirical risk minimization) to be highly non-smooth (e.g. for ReLUs) and non-convex, necessitating special tools such as the Clarke subdifferential (Clarke, 1983).
One of the many exciting results of this body of literature is that gradient-based algorithms exhibit some form of implicit regularization: the optimization algorithm prefers some stationary points to others. In particular, a wide range of implicit biases has been shown in practice (Huh et al., 2021) and proven for deep linear networks (Arora et al., 2018; Ji & Telgarsky, 2019), convolutional neural networks (Gunasekar et al., 2018) and homogeneous networks (Ji & Telgarsky, 2020). One well known result for linearly separable data is that in various practical settings, linear networks converge to the solution of the hard SVM problem, i.e., a max-margin classifier (Ji & Telgarsky, 2019), while a relaxed version is true for CNNs (Gunasekar et al., 2018). This holds even when the margin does not explicitly appear in the optimization objective - hence the name implicit regularization.
Another strong form of implicit regularization relates to the structure of weight matrices of fully connected networks. In particular, Ji & Telgarsky (2019) prove that for deep linear networks for binary classification, weight matrices tend to rank-1 matrices in Frobenius norm as a result of GF/GD training, and that adjacent layers’ singular vectors align. The max-margin phenomenon follows as a result. In practice, Huh et al. (2021) empirically document the low rank bias across different non-linear architectures. However, their results include ReLU fully-connected networks, CNNs and ReNet, which are not all covered by the existing theory. Beyond linear fully connected networks, Du et al. (2018) show vertex-wise invariances for fully-connected ReLU networks and invariances in Frobenius norm differences between layers for CNNs. Yet, despite the evidence in (Huh et al., 2021), it has been an open theoretical question how more detailed structural relations between layers, which, e.g., imply the low-rank result, generalize to other, structured or local nonlinear and possibly non-homogeneous architectures, and how to even characterize these.
Hence, in this work, we take steps to addressing a wider set of architectures and invariances. First, we show a class of vertex and edge-wise quantities that remain invariant during gradient flow training. Applying these invariances to architectures containing fully connected, convolutional and residual blocks, arranged appropriately, we obtain invariances of the singular values in adjacent (weight) matrices. Second, we prove how the controlled singular values imply low-rank results for fully connected ReLU networks. Third, we obtain low-rank results for arbitrary non-homogeneous networks whose last few layers contain fully-connected and ResNet blocks. To the best of our knowledge, this is the first time a low-rank phenomenon is proven rigorously for these architectures.
Our theoretical results offer explanations for empirical observations on more general architectures, and apply to the experiments in (Huh et al., 2021) for ResNet and CNNs. They also include the squared loss used there, in addition to the exponential or logistic loss used in most theoretical low-rank results. Moreover, our Theorem 2 gives an explanation for the “reduced alignment” phenomenon observed by Ji & Telgarsky (2019), where in experiments on AlexNet over CIFAR-10 the ratio ‖W‖2/‖W‖F converges to a value strictly less than 1 for some fully-connected layer W towards the end of the network.
One challenge in the analysis is the non-smoothness of the networks and ensuring an “operational” chain rule. To cope with this setting, we use a specific decomposition of an arbitrary ReLU architecture into a multilinear function and a ReLU network with +1/-1 weights. This reduction holds in the stable sign regime, a certain convergence setting of the parameters. This regime is different from stable activations, and is implied, e.g., by directional convergence of the parameters to a vector with non-zero entries (Lemma 2). This construction may be of independent interest.
In short, we make the following contributions to analyzing implicit biases of general architectures:
• We show vertex and edge-wise weight invariances during training with gradient flow. Using these invariances, we prove that for architectures containing fully-connected layers, convolutional layers and residual blocks, when appropriately organized into matrices, adjacent matrices have the same singular value, up to initialization (Theorem 1).
• We prove that in the stable sign regime, weight matrices in a fully-connected ReLU-activated network tend to rank-1 matrices (Corollary 1). We also show a low-rank bias for arbitrary nonhomogeneous feedforward networks whose last few layers are a composition of fully-connected and ResNet blocks (Theorem 2). In particular, if the Frobenius norms of these layers diverge, then the ratio between their operator norm and Frobenius norm is bounded non-trivially by an expression C fully specified by the architecture. To the best of our knowledge, this is the first time this type of bias is shown for nonlinear, nonhomogeneous networks.
• We prove our results via a decomposition that reduces arbitrarily structured deep feedforward networks with positively-homogeneous activation (e.g., ReLU or linear) to a multilinear structure (Lemma 2).

heading: 1.1 RELATED WORKS
text: Decomposition of fully-connected neural networks into a multilinear part and a 0-1 part has been utilized by Choromanska et al. (2015); Kawaguchi (2016) but their formulation does not apply for trajectory studies. In Section 3, we give a detailed comparison between their approach and ours. Our decomposition makes use of the construction of a tree net that has been used by Khim & Loh (2019) in analyzing generalization of fully-connected networks. We describe their approach in 2 and show how we extend their construction to arbitrary feedforward neural nets. This construction makes up the first part of the proof of our decomposition lemma. The paper also makes use of path enumeration of neural nets, which overlaps with the path-norm literature of Neyshabur et al. (2015; 2017). The distinction is that we are studying classical gradient flow, as opposed to SGD (Neyshabur et al., 2015) or its variants (Neyshabur et al., 2017).
For linear networks, low-rank bias is proven for separable data and exponential-tailed loss in Ji & Telgarsky (2019). Du et al. (2018) give certain vertex-wise invariances for fully-connected ReLU networks and Frobenius norm difference invariances for CNNs. Compared to their results, ours are slightly stronger since we prove that our invariances hold for almost every time t on the gradient flow trajectory, thus allowing for the use of a Fundamental Theorem of Calculus and downstream analysis. Moreover, the set of invariances we show is strictly larger. Radhakrishnan et al. (2020)
show negative results when generalizing the low-rank bias from (Ji & Telgarsky, 2019) to vectorvalued neural networks. In our work, we only consider scalar-valued neural networks performing binary classification.

heading: 2 PRELIMINARIES AND NOTATION
text: For an integer k ∈ N, we write the set [k] := {1, 2, . . . , k}. For vectors, we extend the sign function sgn : R → {−1, 1} coordinatewise as sgn : (xi)i∈[d] 7→ (sgn(xi))i∈[d]. For some (usually the canonical) basis (ei)i∈[n] in some vector space Rn, for all x ∈ Rn we use the notation [x]i = 〈x, ei〉 to denote the i-th coordinate of x.
Clarke subdifferential, definability and nonsmooth analysis. The analysis of non-smooth functions is central to our results. For a locally Lipschitz function f : D → R with open domain D, there exists a set Dc ⊆ D of full Lebesgue measure on which the derivative ∇f exists everywhere by Rademacher’s theorem. As a result, calculus can usually be done over the Clarke subdifferential defined as the set
∂f(x) := CONV { lim i→∞ ∇f(xi) | xi ∈ Dc, xi → x }
where CONV denotes the convex hull.
The Clarke subdifferential generalizes both the smooth derivative when f ∈ C1 (continuously differentiable) and the convex subdifferential when f is convex. However, it only admits a chain rule with an inclusion and not equality, which is though necessary for backpropagation in deep learning.
If one is willing to work with a slightly restricted set of functions - formally known as tame, Whitney stratifiable, path differentiable or definable in an o-minimal structure (Davis et al., 2020; Ji & Telgarsky, 2020; Bolte & Pauwels, 2020), the Clarke subdifferential admits an operational chain rule. All architectures considered in this paper are definable (Ji & Telgarsky, 2020). Here, we use the form from Ji & Telgarsky (2020). Lemma 1 (Lemma B.9 in Ji & Telgarsky (2020)). If f : D open → R is locally Lipschitz and defineable, then for any interval I , arc z : I → D, a.e. t ∈ I , df(z(t))dt = 〈 y, dztdt 〉 ,∀y ∈ ∂f(z(t)) .
Neural networks. Consider a neural network ν : Rd → R. The computation graph of ν is a weighted directed graph G = (V,E,w) with weight function w : E → R. For each neuron v ∈ V , let INv := {u ∈ V : uv ∈ E} and OUTv := {w ∈ V : vw ∈ E} be the input and output neurons of v. Let {i1, i2, . . . , id} =: I ⊂ V and O := {o} ⊂ V be the set of input and output neurons defined as IN(i) = ∅ = OUT(o),∀i ∈ I . Each neuron v ∈ V \I is equipped with a positively-1-homogeneous activation function σv (such as the ReLU x 7→ max(x, 0), leaky ReLU x 7→ max(x, αx) for some small positive α , or the linear activation). To avoid unnecessary brackets, we write we := w(e) for some e ∈ E. We will also abuse notation and write w ∈ RE where E is the set of learnable weights as the vector of learnable parameters. Let P be a path in G, i.e., a set of edges in E that forms a path. We will abuse notation and write v ∈ P for some v ∈ V if there exists u ∈ V such that uv ∈ P or vu ∈ P . Let ρ be the number of distinct paths from any i ∈ I to o ∈ O. Let P := { p1, . . . , pρ } be the enumeration of these paths. For a path p ∈ P and an input x to the neural net, denote xp the coordinate of x used in p.
Given a binary classification dataset { (xi, yi) } i∈[n] with xi ∈ R
d, ‖xi‖ ≤ 1 and yi ∈ {−1, 1}, we minimize the empirical risk R(w) = 1n ∑n i=1 `(yiν(xi)) = 1 n ∑n i=1 `(ν(yixi)) with loss ` : R → R, using gradient flow dw(t)dt ∈ −∂R(w(t)). As we detail the architectures used in this paper, we recall that the activation of each neuron is still positively-homogeneous. The networks considered here are assumed to be bias-free unless stated otherwise. Definition 1 (Feedforward networks). A neural net ν with graph G is a feedforward network if G is a directed acyclic graph (DAG). Definition 2 (Fully-connected networks). A feedforward network ν with graph G is a fullyconnected network if there exists partition of V into V = (I ≡ V1) t V2 t . . . t (VL+1 ≡ O) such that for all u, v ∈ V, uv ∈ E iff there exists i ∈ [L] such that u ∈ Vi and v ∈ Vi+1.
Definition 3 (Tree networks). A feedforward network ν with graph G is a tree network if the underlying undirected graph of G is a tree (undirected acyclic graph).
Examples of feedforwards networks include ResNet (He et al., 2016), DenseNet (Huang et al., 2017), CNNs (Fukushima, 1980; LeCun et al., 2015) and other fully-connected ReLU architectures.
For a fully-connected network ν with layer partition V =: V1 t . . . t VL+1 where L is the number of (hidden) layers, let ni := |Vi| be the number of neurons in the i-th layer and enumerate Vi = {vi,j}j∈[ni]. Weights in this architecture can be organized into matricesW [1],W [2], . . . ,W [L] where Rni+1×ni 3W [i] = ((wvi,jvi+1,k))j∈[ni],k∈[ni+1], for all i ∈ [L]. Tree networks. Most practical architectures are not tree networks, but they have been used to prove generalization bounds for adversarial risks. In particular, for fullyconnected neural networks f whose activations are monotonically increasing and 1- Lipschitz, Khim & Loh (2019) defined the tree transform as the tree network Tf(x;w) =∑nL pL=1 W [L] 1,pL σ ( . . . ∑n2 p2=1 W [2] p3,p2σ ( wp2..pL + ∑n1 p1=1 W [1] p2,p1xp1
)) for vectors w with∏L
j=2 nj entries, indexed by an L-tuple (p2, . . . , pL). We extend this idea in the next section.

heading: 3 STRUCTURAL LEMMA: DECOMPOSITION OF DEEP NETWORK
text: We begin with a decomposition of a neural network into a multilinear and a non-weighted nonlinear part, which will greatly facilitate the chain rule that we need to apply in the analysis. Before stating the decomposition, we need the following definition of a path enumeration function, which computes the product of all weights and inputs on each path of a neural network. Definition 4 (Path enumeration function). Let ν be a feedforward neural network with graph G and paths P = { p1, . . . , pρ } . The path enumeration function h is defined for this network as
h : (x1, x2, . . . , xd) 7→ ( xp ∏ e∈p we ) p∈P where xp := xk such that ik ∈ p.
We first state the main result of this section, proven in Appendix B. Lemma 2 (Decomposition). Let ν : Rd → R be a feedforward network with computation graph G, and ρ is the number of distinct maximal path in G. Then there exists a tree network µ : Rρ → R such that ν = µ ◦ h where h : Rd → Rρ is the path enumeration function of G. Furthermore, all weights in µ are either −1 or +1 and fully determined by the signs of the weights in ν.
Path activation of ReLU networks in the literature. The viewpoint that for every feedforward network ν there exists a tree network µ such that ν = µ ◦ h is not new and our emphasis here is on the fact that the description of µ : Rρ → R is fully determined by the signs of the weights. Indeed, in analyses of the loss landscape (Choromanska et al., 2015; Kawaguchi, 2016), ReLU networks are described as a sum over paths:
ν(x;w) = ∑ p∈P Zp(x;w) ∏ e∈p we = 〈 (Zp(x;w))p∈P , h(x;w) 〉 Rρ , (1)
where Zp(x;w) = 1 iff all ReLUs on path p are active (have nonnegative preactivation) and 0 otherwise. One can then take µ as a tree network with no hidden layer, ρ input neurons all connected to a single output neuron. However, this formulation complicates analyses of gradient trajectories, because of the explicit dependence ofZp on numerical values ofw. In our lemma, µ is a tree network whose description depends only on the signs of the weights. If the weight signs (not necessarily the ReLU activation pattern!) are constant, µ is fixed, allowing for a chain rule to differentiate through it. That weight signs are constant is realistic, in the sense that it is implied by directional parameter convergence (Section 4.1). To see this, compare the partial derivative with respect to some we (when it exists) between the two approaches, in the limit where weight signs are constant
(using Lemma 2) ∂ν/∂we = ∑
p∈P|e∈p
[∇wµ(x;w)]p · xp ∏
f∈p,f 6=e
wf , (2)
(using Zp in Eqn 1) ∂ν/∂we = ∑
p∈P|e∈p
( we∂Zp(x;w)/∂we + Zp(x;w) ) ∏ f∈p,f 6=e wf . (3)
In particular, the dependence of Equation 2 on we is extremely simple. This usefulness of this fact will be made precise in the next section when we study invariances.
Proof sketch. The proof contains two main steps. First, we ‘unroll’ the feedforward network into a tree network that computes the same function by adding extra vertices, edges and enable weight sharing. This step is part of the tree transform in Khim & Loh (2019) if the neural network is a fully-connected network; we generalize it to work with arbitrary feedforward networks. Second, we “pull back” the weights towards the input nodes using positive homogeneity of the activations: a · σ(x) = sgn(a) · σ(x|a|). This operation is done on vertices closest (in number of edges on the unique path between any two vertices in a tree) to the output vertex first and continue until all vertices have been processed. Finally, all the residual signs can be subsumed into µ by subdividing edges incident to input neurons. We give a quick illustration of the two steps described above for a fully-connected ReLU-activated network with 1 hidden layer in the Appendix A.

heading: 4 MAIN THEOREM: TRAINING INVARIANCES
text: In this section, we put the previous decomposition lemma to use in proving an implicit regularization property of gradient flow in training deep neural networks.

heading: 4.1 STABLE SIGN REGIME: A CONSEQUENCE OF DIRECTIONAL CONVERGENCE
text: Recall the gradient flow curve {w(t)}t∈[0,∞) defined by the differential inclusion dw(t)dt ∈ −∂R(w(t)). We first state the main assumption in this section. Assumption 1 (Stable sign regime). For some t0 < tN ∈ [0,∞], we assume that for all t ∈ [t0, tN ), sgn(w(t)) = sgn(w(t0)). If this holds, we say that gradient flow is in a stable sign regime. Without loss of generality, when using this assumption, we identify t0 with 0 and write ”for some t ≥ 0” to mean ”for some t ∈ [t0, tN )”.
In fact, the following assumption - the existence and finiteness part of which has been proven in (Ji & Telgarsky, 2020) for homogeneous networks, is sufficient. Assumption 2 (Directional convergence to non-vanishing limit in each entry). We assume that w(t) ‖w(t)‖2 t→∞−−−→ w exists, is finite in each entry and furthermore, for all e ∈ E,we 6= 0.
Motivation and justification. It is straightforward to see that Assumption 1 follows from Assumption 2 but we provide a proof in the Appendix (Claim 1). Directional convergence was proven by Ji & Telgarsky (2020) using the exponential/logistic loss for the class of homogeneous networks, under additional mild assumptions. This fact justifies the first part of Assumption 2 for these architectures. The second part of Assumption 2 is pathological for our case, in the sense that directional convergence alone does not imply stable signs (for example, a weight that converges to 0 can change sign an infinite number of times).
Pointwise convergence is too strong in general. Note also that assuming pointwise convergence of the weights (i.e. limt→∞ w(t) exists and is finite) is a much stronger statement, which is not true for the case of exponential/logistic loss and homogeneous networks (since ‖w(t)‖2 diverges, see for example Lyu & Li (2020), Ji & Telgarsky (2020), Ji & Telgarsky (2019)). Even when pointwise convergence holds, it would immediately reduce statements on asymptotic properties of gradient flow on ReLU activated architectures to that of linearly activated architectures. One may want to assume that gradient flow starts in the final affine piece prior to its pointwise convergence and thus activation patterns are fixed throughout training and teh behavior (multi)linear. In contrast, directional convergence of the weights does not imply such reduction from the ReLU-activation to the linear case (since, for example, linear pieces of ReLU networks are not necessarily convex (Hanin & Rolnick, 2019) or see a counter-example in Claim 2).
Stable sign implication. The motivation for Assumption 1 is the fact that weights in the tree network µ in the statement of Lemma 2 are fully determined by the signs of the weights in the original feedforward network ν. Thus, under Assumption 1, one can completely fix the weights of µ - it has no learnable parameters. Since we have the decomposition ν = µ ◦ h where h is the
path enumeration function, dynamics of µ are fully determined by dynamics of h in the stable sign regime. To complete the picture, observe that h is highly multilinear in structure: the degree of a particular edge weight we in each entry of h is at most 1 for all edge e by definition of a path; and if ν is fully-connected, then h is a tensor in Rn1×n2×...×nL .

heading: 4.2 TRAINING INVARIANCES
text: First, we state an assumption on the loss function, which holds for most losses used in practice, such as the logistic loss, exponential loss or squared loss. Assumption 3 (Differentiable loss). The loss function ` : R→ R is differentiable everywhere. Lemma 3 (Vertex-wise invariance). Under Assumption 1, and 3, for all v ∈ V \{I ∪ O} such that all edges incident to v have learnable weights, for a.e. time t ≥ 0,∑
u∈INv
w2uv(t)− ∑
b∈OUTv w2vb(t) = ∑ u∈INv w2uv(0)− ∑ b∈OUTv w2vb(0). (4)
If we also have INu = INv = IN and OUTu = OUTv = OUT then for a.e. time t ≥ 0,∑ a∈IN wau(t)wav(t)− ∑ b∈OUT wub(t)wvb(t) = ∑ a∈IN wau(0)wav(0)− ∑ b∈OUT wub(0)wvb(0). (5)
Comparison to Du et al. (2018) A closely related form of Equation 4 in Lemma 3 has appeared in Du et al. (2018) (Theorem 2.1) for fully-connected ReLU/leaky-ReLU networks. In particular, the authors showed that the rate of change of difference between incoming and outgoing weights is 0. Invoking the Fundamental Theorem of Calculus (FTC) over this statement will return ours. However, their proof may not hold over a nonnegligible set of time t due to the use of the operational chain rule (Lemma 1) that holds only for almost all we. Thus the FTC can fail. The stronger form we showed here is useful in proving downstream algorithmic consequences, such as the low rank phenomenon. Furthermore, our result also holds for arbitrary feedforward architectures and not just the fully-connected case.
Before we put Lemma 3 to use, we list definitions of some ResNet variants. Definition 5. Denote ResNetIdentity, ResNetDiagonal and ResNetFree to be the version of ResNet described in He et al. (2016) where the residual block is defined respectively as
1. r(x;U, Y ) = σ(Uσ(Y x) + Ix) where x ∈ Ra, Y, U> ∈ Rb×a, and I is the identity,
2. r(x;U, Y,D) = σ(Uσ(Y x) +Dx) where x ∈ Ra, Y, U> ∈ Rb×a, and D is diagonal,
3. r(x;U, Y, Z) = σ(Uσ(Y x) + Zx) where x ∈ Ra, Y ∈ Rb×a, U ∈ Rc×b and Z ∈ Rc×a.
ResNetIdentity is the most common version of ResNet used in practice and is described in Equation 1 of (He et al., 2016). ResNetFree is described in Equation 2 of (He et al., 2016) but is less commonly used. Note that although ResNetIdentity is a special case of ResNetDiagonal, which is in turn a special case of ResNetFree. However, theorems for ResNetFree, for example, do not generalize trivially to the remaining variants, due to the restriction of Lemma 3 and Lemma 4 to vertices adjacent to all learnable weights and layers containing all learnable weights.
When applying Lemma 3 to specific architectures, we obtain the following: Theorem 1 (Matrix-wise invariances). Recall that a convolutional layer with number of input kernels a, kernel size b and number of output kernels c and is a tensor in Ra×b×c. Under Assumptions 1 and 3, we have the following matrix-wise invariance for a.e. time t ≥ 0:
W2(t) >W2(t)−W1(t)W1(t)> =W2(0)>W2(0)−W1(0)W1(0)> (6)
for:
1. (Fully-connected layers) W1 ∈ Rb×a and W2 ∈ Rc×b consecutive fully-connected layers,
2. (Convolutional layers) W1 is convolutional, viewed as a flattening to a matrix Rc×(a×b), and W2 adjacent convolutional, viewed as a flattening to a matrix R(d×e)×c,
3. (Within residual block of ResNet) W1 = Y and W2 = U where r(x;U, Y, Z) is a residual block of ResNetIdentity, ResNetDiagonal or ResNetFree, 4. (Between residual blocks of ResNet) W1 = [ U1 Z1 ] , W2 = [ Y2 Z2 ] where r(x;Uj , Yj , Zj),
j ∈ {1, 2} are consecutive ResNetFree blocks,
5. (Convolutional-fully-connected layers) W1 convolutional, viewed as a flattening to a matrix Rc×(a×b) and W2 adjacent fully-connected layer, viewed as an rearrangement to Rd×c,
6. (Convolutional-ResNetFree block) W1 convolutional, viewed as a flattening to a matrix Rc×(a×b) and W2 is a rearrangement of [ U Z ] into an element of Rd×c, where r(x;U, Y, Z)
is an adjacent ResNetFree block, 7. (ResNetFree block-fully-connected layers and vice versa) W1 = [ U Z ] ∈ Rb×a and W2 ∈
Rc×b adjacent fully-connected orW1 ∈ Rb×a fully-connected andW2 = [ Y Z ] ∈ Rc×b adjacent
ResNet block where r(x;U, Y, Z) is the ResNetFree block.
We emphasize that the above theorem only makes local requirements on the neural network, to have local parts that are either fully-connected, convolutional or a residual block. The only global architecture requirement is feedforward-ness. The first point of Theorem 1 admits an extremely simple proof for the linear fully-connected network case in Arora et al. (2018) (Theorem 1) but has not been generalized to other architectures.
Significance of Theorem 1. Assume for simplicity that the right hand side in Equation 6 is 0, then the singular values of W1 and W2 are the same for each of the cases listed in Theorem 1. If we can form a chain of matrices whose singular values are the same by iteratively invoking Theorem 1 then all matrices considered have the same singular values as the final fully-connected layer that connects to the output. Recall that our networks are scalar-valued, so the final layer is a row vector, which is rank 1 and thus all layers considered in the chain have rank 1, which is useful in the next section.
Proof sketch of Theorem 1. Given Lemma 3, we demonstrate the proof for the first point. The remaining points admit the exact same proof technique but on different matrices, which can get messy and require some bookkeeping. Let W1 ∈ Rb,a and W2 ∈ Rc,b be two consecutive fullyconnected layers for some a, b, c ∈ N number of vertices in these layers. Apply Equation 4 of Lemma 3 to each of the b shared neurons between these two layers, one get the diagonal entries of Equation 6 of the Theorem. Now, apply Equation 5 to each pair among the b shared neurons between these two layers, one get the off-diagonal entries of Equation 6.
We give a definition of layer for architectures where weights are not necessarily organized into matrices - say ResNet or DenseNet. Definition 6 (Layer). Let F ⊂ E be such that 1) for all e 6= f ∈ F , there is no path that contains both e and f ; and 2) the graph (V,E\F,w) is disconnected. Then F is called a layer of G.
For this definition, we have the following invariance: Lemma 4 (Edge-wise invariance). Under Assumption 1, and 3, for all layers F and F ′ that contains all learnable weights, for a.e. time t ≥ 0,∑
e∈F w2e − ∑ f∈F ′ w2f = ∑ e∈F w2e(0)− ∑ f∈F ′ w2f (0). (7)
Since INo forms a layer, we also have∑ e∈F w2e − ∑ v∈INo w2vo = ∑ e∈F w2e(0)− ∑ v∈INo w2vo(0). (8)
Significance of Lemma 4. A flattening of a convolutional parameter tensor and a stacking of matrices in a ResNetDiagonal and ResNetFree block forms a layer. This lemma implies that the squared Frobenius norm of these matrices in the same network differs by a value that is fixed at
initialization. This lemma also gives a direct implicit regularization for networks with biases, by treating neurons with bias as having an extra in-edge whose weight is the bias, from an extra invertex which is an input vertex with fixed input value 1.

heading: 4.3 PROOF SKETCH OF LEMMA 3 AND LEMMA 4
text: All proofs in Lemma 3, Lemma 4 and Theorem 1 share the same technique of double counting paths, which we explain next. For simplicity, let us here assume that we are working with a network that is differentiable everywhere in some domain that we are considering – we give a full general proof in the Appendix. The main proof idea has been used in (Arora et al., 2018) and involves simply writing down the partial derivative of the risk. We have for some particular weight we, e ∈ E, via the smooth chain rule
∂R(w) ∂we = 1 n n∑ i=1 l′(yiν(xi;w)) · yi · ∂ν(w) ∂we (9)
= 1
n n∑ i=1 l′(yiν(xi;w)) · yi · ∑ p∈P,p3e [ µ′(xi;w) ] p · (xi)p ∏ f∈p,f 6=e wf (10)
where in the second line, we invoke the decomposition Lemma 2 and emphasize that µ has no learnable parameters in the stable sign regime. Now multiply we to the above expression to get
we ∂R(w) ∂we
= ∑
p∈P,p3e
1
n n∑ i=1 Ai,p(w) (11)
where Ai,p(w) = l′(yiν(xi;w)) · yi · [ µ′(xi;w) ] p · (xi)p ∏ f∈p |wf |. Notice that Ai,p(w) does not depend explicitly on the edge e we are taking the partial derivative over (only through w). Thus, we can sum over in-edges and out-edges of a particular v satisfying the assumption of Lemma 3 to get∑
u∈INv
wuv ∂R(w) ∂wuv
= ∑
p∈P,p3v
1
n n∑ i=1 Ai,p(w) = ∑
b∈OUTv
wvb ∂R(w) ∂wvb . (12)
Note that the only difference between Equations 11 and 12 is the set of paths that it is summing over, and we double count this set of paths.
We use the definition of gradient flow to get ∂R(w)/∂we = dwe(t)/dt and integrate with respect to time using a FTC to get the first part of Lemma 3. To get the second part of Lemma 3, we double count the set of jagged paths defined as all paths from I to v together with all paths from u to O and vice versa. Finally, to get Lemma 4, we double count the set of all paths P .

heading: 5 CONSEQUENCES: LOW RANK PHENOMENON FOR NONLINEAR NONHOMOGENEOUS DEEP FEEDFORWARD NET
text: We apply the results from previous parts to prove a low-rank bias result for a large class of feedforward networks. To the best of our knowledge, this is the first time such a result is shown for this class of deep networks, although the linear network analog has been known for some time.
In light of Theorem 1, we have a definition of matrix representations of a layer:
Definition 7 (Matrix representation of a layer). The matrix representation for a ResNetFree block r(x;U, Y, Z) is [ U Z ] ; for a T a,b,c ∈ Ra,b,c convolutional tensor is the flattening to an element of Ra×(b×c); and for a fully-connected layer is the weight matrix itself. Theorem 2 (Reduced alignment for non-homogeneous networks). Under Assumption 1 and 3, let ν consist of an arbitrary feedforward neural network η, followed by K ≥ 0 convolutional layers (T ak,bk,ck)k∈[K], followed by M ≥ 0 layers that are either ResNetFree blocks or fully-connected layers; and finally ending with a linear fully-connected layer Fin. For j ∈ [K +M ], denote W [j] the matrix representation of the j-th layer after η, Nr(j) the number of ResNetFree blocks between
j and Fin exclusively and Vc(j) := maxdimW [M+1] · ∏ j<k≤M min(ak, bk) if j ≤ M and 1 otherwise. Then there exists a constant D ≥ 0 fixed at initialization such that for a.e. time t > 0, 1
8Nr(j)Vc(j) ‖W [j](t)‖2F − ‖W [j](t)‖22 ≤ D, ∀j ∈ [K +M ]. (13)
Furthermore, assume that ‖W [j]‖F → ∞ for some j ∈ [K +M ], then we have, in the limit of t→∞: 1/min ( rank(W [k]), 8Nr(j)Vc(j) ) ≤ ‖W [k](t)‖22/‖W [k](t)‖2F ≤ 1, (14)
where rank returns the number of nonzero singular value of a matrix. In particular, for the last few fully-connected layers j with Nr(j) = 0 and Vc(j) = 1, we have, in the limit of t→∞:∥∥∥∥∥ W [j](t)‖W [j](t)‖F − uj(t)v>j (t) ∥∥∥∥∥ F t→∞−−−→ 0,∀k ∈ [M ], | 〈 vj+1, uj 〉 | t→∞−−−→ 1, (15) where uj and vj is the left and right principal singular vector of W [j]. Corollary 1. For fully-connected networks with ReLU activations, trained with linearly separable data under logistic loss `, under the assumptions thatR(w(0)) < `(0) and the limiting direction of weight vector (which exists (Ji & Telgarsky, 2020)) has no 0 entries, Equation 15 holds.
Significance Equation 13 and its limiting counterpart Equation 14 quantifies a low-rank phenomenon by providing a lower bound on the ratio of the largest squared singular value (the operator norm) to the sum of all squared singular values (the Frobenius norm). This lower bound depends on the number (not dimensions) of ResNetFree layers (Nr) and certain dimensions of convolutional layers (Vc). When the dimensions of ResNetFree layers are large, maxdimW [M+1] is small and number of input channels of convolutional layers are large, this lower bound is strictly better than the trivial lower bound of 1/rank(W [k]). This is a quantification of the reduced alignment observed in (Ji & Telgarsky, 2019). In particular, for the last few fully connected layers (Equation 15, Corollary 1), the lower bound matches the upper bound of 1 in the limit of Frobenius norm tending to infinity and the limiting weight matrices have rank 1 and adjacent layers align.

heading: 5.1 PROOF SKETCH
text: The proof is similar to that of Lemma 2.6 in (Ji & Telgarsky, 2019). Fix a j ∈ [M + 1] and invoke Lemma 4 over the layer W [j] to get ‖W [j]‖2F − ‖Fin‖2F = D1 for some D1 fixed at initialization. But since our network is scalar-valued, Fin is a vector and thus ‖Fin‖2F = ‖Fin‖22. Now invoking Theorem 1 for consecutive pairs of layers, we can prove that ‖W [k]‖22 ≥ C‖W [k+1]‖22 − D2,k for C = 1/8 if the k + 1 layer is a ResNetFree block (Lemma 10), C = 1/min(ak+1, bk+1) if the k + 1 layer is a convolutional layer, C = maxdimW [M+1] if k = M (Lemma 9) and C = 1 otherwise, for some D2,k fixed at initialization, for all k from j to M +K. Telescope and subtract from ‖W [j]‖2F to get the final result. The rest follows from Lemma 2.6 in (Ji & Telgarsky, 2019).

heading: 6 CONCLUDING REMARKS AND FUTURE DIRECTIONS
text: In this paper, we extend the proof of the low rank phenomenon, which has been widely observed in practice, beyond the linear network case. In particular, we address a variety of nonlinear architectural structures, homogeneous and non-homogeneous, which in this context have not been addressed theoretically before. To this end, we decomposed a feedforward ReLU/linear activated network into a composition of a multilinear function with a tree net. If the weights converge in direction to a vector with non-zero entries, the tree net is eventually fixed, allowing for chain rules to differentiate through. This leads to various matrix-wise invariances between fully-connected, convolution layers and ResNet blocks, enabling us to control the singular values of consecutive layers. In the end, we obtain a low-rank theorem for said local architectures.
Proving convergence to stable sign regime for wider architectures will strengthen Theorem 2. Another direction is to connect our low-rank bias results to the max-margin implicit regularization literature, which has been shown for linear networks and, more recently, certain 2-homogeneous architecture (Ji & Telgarsky, 2020). Another direction is to extend alignment results to vector-valued neural nets, where Radhakrishnan et al. (2020) gave a certain negative results.

heading: B PROOF OF LEMMA 2
text: We first prove an absolute-valued version of Lemma 2 and show that the extension to Lemma 2 is straightforward. In other words, we first prove Lemma 5 (Absolute-valued decomposition). For an arbitrary feed-forward neural network ν : Rd → R, there exists a tree network µ′ : Rρ → R such that ν = µ′ ◦ h′ where h′ is the absolute-valued path enumeration function defined as h′(x) = ( xp ∏ e∈p |we| ) p∈P . Furthermore, the weights of µ′ is in {−1, 1} and only depends on the sign of the weights of the original network ν.
We first give some extra notation for this section. In general, we define:
• ℘(S) to be the finite power set of some finite set S.
• |p| ∈ N≥0 to be the cardinality of a set p. When p is a path then it is viewed as the number of edges.
To make it clear which graph we are referring to, define for an arbitrary feedforward neural network ν : Rd → R with computation graph G = (G[V ], G[E], G[w]):
• IG = {iG1 , . . . , iGd } to be the set of input node of G and OG = {oG} to be the set of the single output node of G.
• PG to be the enumeration of all paths from any input node in IG to the output node oG. • HG to be the enumeration of all paths from any node v ∈ G[V ] to the output node oG.
Note that if G has more than 2 vertices thenHG ⊃ PG. • Each v ∈ G[V ] to be equipped with a fix activation σv that is positively-1-homogeneous.
To be precise, G is enforced to be a DAG, is connected and is simple (no self-loop, at most 1 edge between any pair of vertices). Each node v of G[V ] is equipped with: an activation function G[σ](v) that is positively-1-homogeneous; a pre-activation function defined as:
(G[PRE](v))(x) = { xj if v ≡ iGj for some j ∈ [d]∑ u∈INv POSTv(x)wuv otherwise;
(16)
and a post-activation function defined as
(G[POST](v))(x) = σv((G[PRE](v))(x)) (17)
Note that POSToG = ν.
• vGp , eGp to be the vertex and edge, respectively, furthest from oG on some path p of G.
• xGp to be the unique xj such that iGj ∈ p.
Definition 8 (Hasse diagram of inclusion). Let S be a finite set and a set S ⊂ ℘(S) of elements in S. A Hasse diagram of S is a directed unweighted graph HASSE(S) = (S, E) where for any p, q ∈ S, pq ∈ E iff p ⊆ q and |q| − |p| = 1. Definition 9 (Unrolling of feedforward neural networks). The unrolled tree neural network τG of G is a tree neural network with computation graph TG where
• Unweighted graph (TG[V ], TG[E]) = HASSE(HG). In particular TG[V ] = HG and we identify vertices of TG with paths in G.
• Weight function TG[w] : TG[E] 3 pq 7→ G[w](ep).
• Activation TG[σ](v) := G[σ](vp). Lemma 6 (Unrolled network computes the same function). Fix an arbitrary feedforward neural network ν : Rd → R with computation graph G. Let τG be the unrolled tree network of G with computation graph TG. Then ν = τG.
Proof. We proceed with induction on αG := maxp∈P |p| the longest path between any input node and the output node of G. In the base case, set αG = 0. Then VG = {oG} is a singleton and the neural network ν computes the activation of the input and return it. HG = VT = {p0} then is a singleton containing just the trivial path that has just the output vertex of G and no edges. The activation function attached to p0 in T , by construction, is the activation of oG. Thus, τ also simply returns the activation of the input.
Assume that τG = ν for any ν with graph G such that αG ≤ t − 1 for some t ≥ 1; and for the τ constructed as described. We will show that the proposition is also true when ν has graph G with αG = t. Fix such a ν and G that αG = t. We prove this induction step by:
1. First constructing G′ from G such that ν′ = ν where ν′ is the neural network computed by G′.
2. Then showing that TG = G′ by constructing an isomorphism π : G′[V ] → TG[V ] that preserves E,w and σ.
The construction of G′ An illustration of the following steps can be found in Figure 3. Recall that INoG = {v1, . . . , vm} is the set of in-vertices of oG.
1. Create m distinct, identical copies of G: G1, . . . , Gm.
2. For each j ∈ [m], remove from Gj all vertices u (and their adjacent edges) such that there are no directed path from u to vj .
3. We now note that αGj ≤ t − 1 (to be argued) and invoke inductive hypothesis over Gj to get an unrolled tree network τj with graph Tj such that τj = νj where νj is the neural network computed by Gj .
4. Finally, construct G′ by creating a new output vertex oG′ and connect it to the output vertices oTj for all j ∈ [m]. As a sanity check, since each Tj is a tree network, so is G′. More precisely,
(a) G′[V ] = {oG′} ∪ ⋃m j=1 Tj [V ];
(b) G′[E] = {oGjoG′ | j ∈ [m]} ∪ ⋃m j=1 Tj [E] (c) G′[w](e) = G[w](vjoG) if e ≡ oGjoG′ for some j ∈ [m] and Tj [w](e), where e ∈ Tj [E], otherwise. (d) G′[σ](v) = G[σ](oG) if v ≡ oG and Tj [σ](v), where v ∈ Tj [V ], otherwise.
G′ is well-defined We verify each steps in the above construction:
1. This step is well-defined.
2. For any Gj , as long as αG ≥ 2 (by definition), we always remove oG from each Gj in each step; since vj is an in-vertex of oG and G is a DAG. Otherwise, this step is well-defined.
3. Fix a j ∈ [m]. By construction (and since we always remove oG from Gj in the previous step), OGj = {vj}. If there is a path p∗ with length at least t in Gj , then since Gj [E] ⊆ G[E] and oG ∈ G[V ] \ Gj [V ], the path p∗ ∪ {oG} created by appending oG to p∗ is a valid path with length t + 1. This violates the assumption that αG = t and we conclude, by contradiction, that αGj ≤ t− 1. This justifies the invocation of inductive hypothesis for νj to get a tree neural net τj .
4. The final step is well-defined.
ν′ computes the same function as ν Recall that ν′ is the neural network with graph G′. We have for any input x ∈ Rd
ν′(x) = (G′[POST](oG′))(x) (18)
= G′[σ](oG′)  m∑ j=1 G′[w](vjoG′) · (G′[POST](vj))(x)  (19) = G[σ](oG)
 m∑ j=1 G[w](vjoG) · (Tj [POST](vj))(x)  (20) = G[σ](oG)
 m∑ j=1 G[w](vjoG) · (G[POST](vj))(x)  = ν(x) (21) where we invoked the inductive hypothesis in the last line to get
(Tj [POST](vj))(x) = τj(x) = νj(x) = (G[POST](vj))(x), (22)
and the rest are definitions.
G′ is isomorphic to TG Although this should be straightforward from the construction, we give a formal proof. Consider the isomorphism π : G′[V ]→ TG[V ] given as
π(v) = { oTG = {oG} ∈ HG if v ≡ oG′ p ∪ {oG} if Tj [V ] 3 v ≡ p ∈ HGj for some j ∈ [m],
(23)
where paths are viewed as set of vertices. The second case is well-defined since p∪ {oG} ∈ HG for any p ∈ HGj for any j ∈ [m] by construction of Gj . We can now verify that π is an isomorphism between the two structures. Fix pq ∈ G′[E]. Consider two separate cases: pq ∈ Tj [E] for some j and pq 6∈ Tj [E] for any j. In the first case, by definition of Tj as a Hasse diagram, p = {vp} ∪ q are paths in HGj . Thus, π(p)π(q) = (p ∪ {oG})(q ∪ {oG}) satisfying π(p) = {vp} ∪ π(q). Thus, by definition of Hasse diagram, π(p)π(q) ∈ TG[E]. Furthermore, G′[w](pq) = G[w](ep) = TG[w](π(p)π(q)) In the second case, we have pq = vjoG for some j ∈ [m]. Thus, π(p)π(q) = ({vj , oG})({oG}) ∈ TG[E] also by definition of Hasse diagram. At the same time, G′[w](pq) = G[w](vjoG) = TG[w](π(p)π(q)) by definition.
Fix v ∈ G′[V ]. If v ≡ oG′ then G′[σ](v) = G[σ](oG). At the same time, TG[σ](π(v)) = G[σ](v{oG} = G[σ](oG) = G
′[σ](v). If v 6≡ oG′ then there is a j ∈ [m] and a p ∈ HGj such that v = p ∈ Tj [V ]. Then by definition,
G′[σ](v) = Tj [σ](v) = G[σ](vp) = G[σ](vp ∪ {oG′}) = TG[σ](π(v)). (24)
This completes the inductive proof that shows τG = ν′ = ν for G with αG = t. By mathematical induction, the claim holds for all neural network ν.
Lemma 7 (Pull-back of numerical weights). Fix an arbitrary feedforward neural network ν : Rd → R with computation graph G. Let v ∈ G[V ] \ (IG ∪ OG) be an inner vertex of G with k in-edges e1, . . . , ek ∈ G[E] and a single out-edge f ∈ G[E]. Then the network ν′ with computation graph G′ = (G[V ], G[E], G′[w]) defined as
G′[w] : e 7→  G[w](e)|G[w](f)| if e ≡ ej for some j ∈ [k] sgn(G[w](f)) if e ≡ f G[w](e) otherwise.
(25)
computes the same function as ν. In other words, we can pull the numerical values of G[w](f) through v, into its in-edges; leaving behind only its sign.
When fixing input x toG, one can extend this operation to ij ∈ IG for j ∈ [d]. By settingG′[w](f) = sgn(G[w](f)) and update xj to xj |G[w](f)|.
Proof. Let the single out-vertex of v be b. If suffices to show that G[PRE](b) = G′[PRE](b). Fix an input x to ν. Let the k in-edges of v be a1, . . . , ak. Since we only change edges incident to v, G[POST]aj = G ′[POST]aj for all j ∈ [k]. We have:
G′[PRE](b) = sgn(G[w](vb)) · (G[σ](v))(G′[PRE](v)) (26)
= sgn(G[w](vb)) · (G[σ](v))  k∑ j=1 |G[w](vb)|G[w](ajv) ·G[POST](aj)  (27) = sgn(G[w](vb))|G[w](vb)| · (G[σ](v))
 k∑ j=1 G[w](ajv) ·G[POST](aj)  (28) = G[w](vb) · (G[σ](v))
 k∑ j=1 G[w](ajv) ·G[POST](aj)  = G[PRE](b), (29) where equation 28 is due to positive homogeneity of σv and the rest are just definitions.
We can now give the proof of Lemma 5.
Proof of Lemma 5. Given an arbitrary feedforward neural network ν with computation graph G = (G[V ], G[E], G[w]), we use Lemma 6 and get the unrolled tree network TG = (TG[V ], TG[E], TG[w]) such that ν = τG.
Let π = π1, π2, . . . , πξ be an ordering of TG[V ] \ OTG (so ξ = |H| − 1) by a breadth first search on TG starting from oTG . In other words, if dtopo(u, oTG) > dtopo(v, oTG) then u appears after v in π, where dtopo(a, b) is the number of edges on the unique path from a to b for some a, b ∈ TG[V ]. Iteratively apply Lemma 7 to vertex π1, . . . , πξ in TG while maintaining the same function. After ξ such applications, we arrive at a network µ′G with graph MG such that µ ′ G = τG = ν. Recall that the pull-back operation of Lemma 7 only changes the tree weights. Furthermore, the π ordering is chosen so that subsequent weight pull-back does not affect edges closer to oTG . Therefore, at iteration j,
1. MG[w](πkq) = sgn(G[w](eπk)) for all k ≤ j, for some q ∈ MG[V ] such that (πk)q ∈ MG[E].
2. if πj 6∈ IMG then MG[w](r(πj)) = G[w](er) ∏ f∈πj |G[w](f)|, for some r ∈ MG[V ]
such that r(πj) ∈ MG[E]; otherwise, πj is an input vertex corresponding to input xπj , then xπj is modified to xπj ∏ f∈πj |G[w](f)| = h ′ G(xπj ) where h ′ G is the absolute-valued path enumeration function.
This completes the proof.
Now we present the extension to Lemma 2:
Proof of Lemma 2. Invoke Lemma 5 to get a tree network µ′ such that ν = µ′ ◦ h′. Then one can subdivide each input edges (edges that are incident to some input neuron ij) into two edges connected by a neuron with linear activation. One of the resulting egde takes the weight of the old input edge; and the other is used to remove the absolute value in the definition of the (basic) path enumeration function.
More formally, for all p ∈ P , recall that ip is a particular input neuron of µ′ in the decomposition lemma (Lemma 2). Since µ′ is a tree neural network, we there exists a distinct node up in µ′ that is adjacent to ip. Remove the edge ipup, add a neuron u′p, connect ipu ′ p and u ′ pup, where the weight
of the former neuron is set to sgn (∏
e∈p we ) and the latter to w[µ′](ipup). It is straightforward to
see that with µ constructed from above, ν = µ ◦ h where h is the path enumeration function.
With slight modifications to the proof technique, one can show all the results for Theorem 1, Theorem 2 and Corollary 1 to the same matrix representation as presented in the paper but with the absolute signs around them.

heading: C PROOF OF TRAINING INVARIANCES
text: Claim 1 (Directional convergence to non-vanishing point implies stable sign). Assumption 2 implies Assumption 1.
Proof. Let v be the direction that w(t)‖w(t)‖2 converges to. Let O be the orthant that v lies in. Since v does not have a 0 entry, the ball B with radius mini |vi|/2 and center v is a subset of the interior of O. Since w(t)‖w(t)‖2 converges to v, there exists a time T such that for all s > T, w(s) ‖w(s)‖2 ∈ B. Thus, eventually, w(s) ∈ B where its signs stay constant.
Claim 2 (Directional convergence does not imply stable activation). There exists a functionw : R→ Rd such thatw(t) converges in direction to some vector v but for all u ∈ w(R),w−1(u) has infinitely many elements. This means that for some ReLU network empirical risk function R(w) whose set of nondifferentiable points D has nonempty intersection with w(R), the trajectory { w(t) } t≥0 can cross a boundary from one activation pattern to another an infinite number of times.
Proof. Fix a vector v ∈ Rd. Consider the function t 7→ v|t sin(t)|.
Proof of Lemma 3. Recall that our real weight vector w(t) is an arc Ji & Telgarsky (2020) which, by definition, is absolutely continuous. It then follows from real analysis that its component we(t) is also absolutely continuous for any e ∈ E. For absolutely continuous functions we(t) for some e ∈ E, invoke the Fundamental Theorem of Calculus (FTC) (Chapter 6, (Heil, 2019)), to get:∑
u∈INv w2uv(t)− ∑ u∈INv w2uv(0) = 2 ∑ u∈INv ∫ [0,t] wuv(s) dwuv dt (s)ds (30)
We now proceed to compute dwdt (s). Since w(t) is absolutely continuous and we are taking the integral via FTC, we only need to compute dwdt (s) for a.e. time s. By chain rule (see for example, the first line of the proof of Lemma C.8 in Lyu & Li (2020)), there exists functions (gj)nj=1 such that gj ∈ ∂νxj (w) ⊆ R|E| for all j ∈ [n] where νxj (w) = ν(xj ;w), and for a.e. time s ≥ 0,
dw dt (s) = 1 n n∑ j=1 l′(yjν(xj ;w(s))) · yj · gj (31)
Fix j ∈ [n], by the inclusion chain rule, since νxj = µ ◦ hxj , with h and µ also locally Lipschitz, we have by Theorem I.1 of Lyu & Li (2020),
∂νxj (w) = ∂(µ ◦ hxj )(w) ⊆ CONV ∑ p∈ρ [α]ρβj,ρ | α ∈ ∂µ(h(w)), βj,ρ ∈ ∂[hxj ]p(w)  . (32) Thus there exists (γa)Aa=1 ≥ 0, ∑A a=1 γa = 1 and (α
a ∈ ∂µ(h(w)), βaj,p ∈ ∂[hxj ]p(w))Aa=1 such that:
gj = A∑ a=1 γa ∑ p∈ρ [αa]pβ a j,p.
Here we use Assumption 1 to deduce that eventually, all weights are non-zero in gradient flow trajectory to compute:
∂[hxj ]p(w) =
{ d[hxj ]p(w)
d(w)
} =  1e∈p · sgn(we) · (xj)p ∏
f∈p,f 6=e
|wf |  e∈E  .
Plug this back into gj to get:
gj =  A∑ a=1 γa ∑ p∈ρ|e∈p [α]apsgn(we) · (xj)p ∏ f∈p,f 6=e |wf |  e∈E .
Plug this back into dwdt (s) and to get, coordinate-wise, for a.e. s ≥ 0,
dwe dt (s) = 1 n n∑ j=1 l′(yiν(xi;w(s)))·yi· A∑ a=1 γa ∑ p∈ρ|e∈p [αa]psgn(we(s))·(xj)p ∏ f∈p,f 6=e |wf (s)|. (33)
Multiply both sides with we gives:
we(s) dwe dt
(s) = ∑
p∈P|e∈p
1
n n∑ j=1 dj,p(w(s)), (34)
where
dj,p(w) = l ′(yiν(xi;w)) · yi · A∑ a=1 γa[α] a p · (xj)p · ∏ f∈p |wf (s)|. (35)
Note that d does not depend on the specific edge e used in Equation 33.
Plugging back into the FTC to get:∑ u∈INv w2uv(t)− ∑ u∈INv w2uv(0) = 2 ∑ u∈INv ∫ [0,t] ∑ p∈P|uv∈p 1 n n∑ j=1 dj,p(w(s))ds (36)
= 2 ∫ [0,t] ∑ p∈P|v∈p 1 n n∑ j=1 dj,p(w(s))ds. (37)
Finally, by an identical argument but applied to the set of edges vbfor some b ∈ OUTv , we have:∑ b∈OUTv w2vb(t)− ∑ b∈OUTv w2vb(0) = 2 ∫ [0,t] ∑ p∈P|v∈p 1 n n∑ j=1 dj,p(w(s))ds (38)
= ∑ u∈INv w2uv(t)− ∑ u∈INv w2uv(0), (39)
which completes the proof of the first part of the lemma.
For the second part, recall that we have 2 vertices u, v such that INv = INu = IN and OUTv = OUTu = OUT. Use 33 to get, for notations set up previously, for almost every time s > 0,∑
a∈IN sgn(wau(s)wav(s))
( wau(s)
dwav dt (s) + dwau dt (t)wav(t) ) = ∑ p∈A 1 n n∑ j=1 dj,p(w(s)), (40)
where A is a set of jagged paths (Figure 4) defined as A = { p1 ∪ p2|p1 is a path from I to v or u; p2 is a of path from u or v, respectively, to O } .
Then by a double counting argument, we also have∑ b∈OUT sgn(wub(s)wvb(s)) ( wub(t) dwvb dt (t) + dwub dt (t)wvb(t) ) (41)
= ∑ p∈A 1 n n∑ j=1 dj,p(w(s)) (42)
= ∑ a∈IN sgn(wau(s)wav(s)) ( wau(t) dwav dt (t) + dwau dt (t)wav(t) ) . (43)
Integrate both sides over [0, t] as we did in the first part to get the conclusion of the second part. Note that the second part is special case of the first part, which is obtainable by setting u = v. We point out that proof of the first and second part of this lemma differs only in the choice of the set A (in the first part, A is the set of all paths that goes through v).
Proof of Lemma 4. The proof is identical to that of Lemma 3, with the only difference being the set A that we double count. Here, set A to be P . Then by the definition of layer (see Definition 6), one can double count P by counting paths that goes through any element of a particular layer. The proof completes by considering (using the same notation as the proof of Lemma 3) for a.e. time s ≥ 0,∑
e∈F we(s)
dwe dt (s) = ∑ p∈P 1 n n∑ j=1 dj,p(w(s)) · (xj)p · ∏ f∈p |wf (s)|, (44)
for any layer F .
Before continuing with the proof of Theorem 1, we state a classification of neurons in a convolutional layer. Due to massive weight sharing within a convolutional layer, there are a lot more neurons and edges than the number of free parameters in this layer. Here, we formalize some concepts:
Definition 10 (Convolutional tensors). Free parameters in a (bias-free) convolutional layer can be organized into a tensor T ∈ Ra×b×c where a is the number of input channels, b is the size of each 2D filter and c is the number of output channels.
For example, in the first convolutional layer of AlexNet, the input is an image with 3 image channels (red, blue and green), so a = 3 in this layer; filters are of size 11 × 11 so b = 121 is the size of each 2D filter; and finally, there are 96 output channels, so c = 96. Note that changing the stride and padding does not affect the number of free parameters, but does change the number of neurons in the computation graph of this layer. Thus, we need the following definition:
Definition 11 (Convolutional neuron organization). Fix a convolutional layer with free parameters T ∈ Rc×b×a. Then neurons in this layer can be organized into a two dimensional array {vj,k}j∈[l],k∈[c] for some l ∈ N such that
1. For all j, j′ ∈ [l] and for all k ∈ [c], vj,k and vj′,k share all its input weights. More formally, there exists a bijection φ : INvj,k → INvj′,k such that:
wuvj,k ≡ wφ(u)vj′,k , (45)
for all u ∈ INvjk .
2. For all j ∈ [l] and for all k, k′ ∈ [c], vj,k and vj,k′ has the same in-vertices and out-vertices. In other words,
INvjk = INvj,k′ =: INvj and OUTvjk = OUTvj,k′ =: OUTvj . (46)
For example, in the first convolutional of AlexNet in R96×121×3, the input image dimension is 224 × 224 × 3 pixels and the stride of the 11 × 11 × 3 filters in the layer is 4, with no padding. Thus a single 2D filter traverse the image ( 224−(11−4)
4
)2 =: l times, each corresponds to a different
neuron in the layer. This process is then repeated c times for each output channel, for a total of c× l neurons in the convolutional layer. Lemma 8 (Extension of Lemma 3 to weight sharing). Let V := {vj,k}j∈[l],k∈{1,2} be a convolutional neuron organization. Recall that by definition 11, for all j ∈ [l], INvj,1 = INvj,2 =: INj and OUTvj,1 = OUTvj,2 =: OUTj . We have for a.e. time t ≥ 0,∑
(w,w′)∈wIN(V)
|w(t)w′(t)| − |w(0)w′(0)| = ∑
(z,z′)∈wOUT(V)
|z(t)z′(t)| − |z(0)z′(0)|, (47)
where
wIN(V) := {(w1, w2) | ∀j ∈ [l],∃aj ∈ INj , wajvj,1 ≡ w1 and wajvj,2 ≡ w2},
and similarly,
wOUT(V) := {(w1, w2) | ∀j ∈ [l],∃bj ∈ OUTj , wvj,1bj ≡ w1 and wvj,2bj ≡ w2}.
Before we start the proof, some remarks are in order. Let T1 ∈ R2×b×a be a convolutional layer and let V = {vj,k}j∈[l],k∈[2] be its convolutional neuron organization. Then
wIN(V) = {([T1]1,j2,j1 , [T1]2,j2,j1) | j1 ∈ [a], j2 ∈ [b]}. (48)
If furthermore T2 ∈ Re×d×2 is a convolutional layer immediately after T1, then
wOUT(V) = {([T2]k1,k2,1, [T2]k1,k2,2) | k1 ∈ [e], k2 ∈ [d]}. (49)
If instead of T2, the subsequent layer to T1 is a fully-connected layer W ∈ Rd×(l×2) (recall that there are 2l neurons in T1 layer), then
wOUT(V) = {(Wl1,l2×1, [T2]l1,l2×2) | l1 ∈ [d], l2 ∈ [l]}. (50)
Proof of Lemma 8. As before, the proof is identical to that of Lemma 3 with the exception being the set of paths that we are double counting over. For all j ∈ [l], let
Aj := {p1 ∪ p2 | p1 is a path from I to vj,1 , p2 is a path from vj,2 to o}, (51)
and A′j := {p1 ∪ p2 | p1 is a path from I to vj,2 , p2 is a path from vj,1 to o}. (52)
Let A := ⋃ j∈[l]Aj ∪ A′j . Then by an identical argument as that of Lemma 3, we can show that∑
(w,w′)∈wIN(V)
|w(t)w′(t)| − |w(0)w′(0)| = ∫ [0,t] ∑ p∈A 1 n n∑ j=1 dj,p(w(s))ds (53)
= ∑
(z,z′)∈wOUT(V)
|z(t)z′(t)| − |z(0)z′(0)|. (54)
Proof of Theorem 1. All points in this theorem admit the same proof technique: First, form the matrices as instructed. Let X = {v1, v2, . . . , vm} ⊆ V be the neurons shared between the two layers. Check the conditions of the second part of Lemma 3 and invoke the lemma for each pair u, v ∈ X . We now apply this to each points:
1. Let W1 ∈ Rb×a be a fully-connected layer from neurons in V1 to neurons in V2 and W2 ∈ Rc×b be a fully-connected layer from V2 to V3. Then we have INu = V and OUTu = W for all u ∈ U . Furthermore, all weights around any u are learnable for all u in U . Invoke the second part of Lemma 3 to get the conclusion.
2. let T1 ∈ Rc×b×a and T2 ∈ Re×d×c be the convolutional tensors with convolutional neuron organization of T1 (Definition 11) being {vj,k}j∈[l1],k∈[c]. Form the matrix representation W1 ∈ Rc×(ab) and W2 ∈ R(de)×c as per the theorem statement. By Definition 11, for k, k′ ∈ [c], for all j ∈ [l], INvj,k = INvj,k′ and OUTvj,k = OUTvj,k′ . Invoke Lemma 8 to get the conclusion.
3. Let r(x;U, Y, Z) be a residual block of either ResNetIdentity, ResNetDiagonal or ResNetFree. In all variants, skip connection affects neither the edges in U ∈ Rb×a and Y ∈ Rc×b. Let Y be fully-connected from neurons V1 to neurons V2 and U be fully-connected from neurons V2 to neurons V3. Then for each u ∈ V2, INu = V1 and OUTu = V3. Furthermore, all weights around any vertices in V2 are learnable. Invoke the second part of Lemma 3 to get the conclusion.
4. Let ri(x;Ui, Yi, Zi), i ∈ {1, 2} be consecutive ResNetFree block. Let Y1 be fully connected from neurons V1 to neurons V2, U1 be fully-connected from V2 to neurons V3, Y2 be fully-connected from neurons V3 to V4 and U2 be fully-connected from V4 to neurons V5.
Then [ U1 Z1 ] is fully-connected from V1 ∪ V2 to V3 and [ Y2 Z2 ] is fully-connected from V3 to V4 ∪ V5. Invoke the first point to get the conclusion.
5. Let the convolutional tensor be T ∈ Rc×b×a with convolutional neuron organization {vj,k}j∈[l],k∈[c] for some l ∈ N. Let the adjacent fully-connected layer be W ∈ Rd×(l×c). Form the matrix representation W1 ∈ Rc×ab and W2 ∈ Rdl×c as per the theorem statement. Then we have for any k, k′ ∈ [c] and for all j ∈ [l], INvj,k = INvj,k′ =: INj and OUTvj,k = OUTvj,k′ =: OUTj . Invoke Lemma 8 to get the conclusion.
6. Let r(x;U, Y, Z) be a residual block of either ResNetIdentity, ResNetDiagonal or ResNetFree. Let Y be fully-connected from neurons V1 to neurons V2, U be fully-connected from neurons V2 to neurons V3. Thus, Z is fully-connected from V1 to V3. Then W2 = [ U Z ] is fully connected from V1 to V2 ∪ V3.We invoke the fifth point to get the conclusion.
7. first consider the case where the ResNetFree block is followed by the fully-connected layer. Let r(x;U, Y, Z) be the first ResNetFree block with input neurons where Y fully-connects neurons V1 to V2 and U fully connects V2 to V3. Then we have [ U Z ] fully-connects
V1∪V2 to V3. If the subsequent layer is a fully-connected layer then invoke the first point to get the conclusion; otherwise if the subsequent layer is a ResNetFree block r(x;U ′, Y ′, Z ′) with Y ′ fully-connects V3 to V4 and U ′ fully-connects V4 to V5. Then [ Y Z ] fully-connects V3 to V4 ∪ V5 and we one again invoke the first point to get the conclusion.

heading: D PROOF OF THEOREM 2
text: First we state a helper lemma
Lemma 9 (Largest singular value of different flattening of the same tensor is close). Let T ∈ Ra,b,c be an order 3 tensor (say a convolutional weight tensor). Let T1, T2 be the standard flattening of this tensor into an element in Rc×(a×b) and R(b×c)×a respectively. Then,
1
min(a, b) ‖T1‖22 ≤ ‖T2‖22. (55)
Proof. Invoke Theorem 4.8 of Wang et al. (2017) and using the same notation in the same paper, we have for π1 = {{c}, {a, b}} and π2 = {{b, c}, {a}},
dimT (π1, π2)
dim(T ) ‖T1‖22 ≤ ‖T2‖22. (56)
All that is left is to compute the left hand side in term of a, b, c. By definition, dim(T ) = abc and
dimT (π1, π2) = dimT ({{c}, {a, b}}, {{b, c}, {a}}) (57) = [ max ( DT ({c}, {b, c}), DT ({c}, {a} )] (58)
· [ max ( DT ({a, b}, {b, c}), DT ({a, b}, {a}) )] (59)
= [ max(c, 0) ] · [ max(a, b) ] = cmax(a, b). (60)
Plug this in equation 56 to get the final result.
Lemma 10 (Shuffling layer in ResNetFree block preserves largest singular value up to multiple by 8). Recall that for a ResNetFree block r(U, Y, Z) with Y ∈ Rb×a, U ∈ Rc×b and Z ∈ Rc×a, there
are two possible rearrangement of the weights A = [ U Z ] and B = [ Y Z ] . We have ‖B‖22 ≥
1 8‖A‖ 2 2 −D′ where D′ ≥ 0 is fixed at inialization.
Proof. Recall that by point three of Theorem 1, we have matrix invariance
U>(t)U(t)− Y (t)Y >(t) = U>(0)U(0)− Y (0)Y >(0).
By line B.2 in Ji & Telgarsky (2019),
‖Y ‖22 ≥ ‖U‖22 −D, (61)
where D = ‖U>(0)U(0)− Y (0)Y >(0)‖22 is fixed at initialization. For positive semidefinite matrixX , denote λ(X) to be the function that returns the maximum eigenvalue of X . We have
‖B‖22 = (λ(B>B))2 (62)
= ( λ ( Y >Y + Z>Z ))2 (63)
≥ 1 4
( λ ( Y >Y ) + λ ( Z>Z ))2 (64)
≥ 1 4
( λ ( Y >Y ))2 + 1
4
( λ ( Z>Z ))2 (65)
≥ 1 4
( λ ( UU> ))2 + 1
4
( λ ( ZZ> ))2 − D
4 (66)
≥ 1 8
( λ ( UU> ) + λ ( ZZ> ))2 − D
4 (67)
≥ 1 8
( λ ( UU> + ZZ> ))2 − D
4 (68)
= 1
8
( λ ( AA> ))2 − D
4 =
1 8 ‖A‖22 − D 2 , (69)
where 64 is by an application of Weyl’s inequality for Hermitian matrices which states that λ(C + D) ≥ λ(C) + t where t is is the smallest eigenvalue of D, which is nonnegative since matrices here are all positive semidefinite; 66 is a consequence of 61 and 68 is the application of the inequality λ(C +D) ≤ λ(C) + λ(D) which is another of Weyl’s inequality for Hermitian matrices.
Proof of Theorem 2. Fix j ∈ [K +M ], similar to the proof of Theorem 1, we first invoke Lemma 4 to bound the Frobenius norm of each of the final K +M + 1 layers (counting the last layer Fin) via the last layer. Let Wj be the matrix representation of the j-th layer among the last M + 1 layer as described in Theorem 1. Note that even if a layer has more than one matrix representation
in Theorem 1, their Frobenius norm is still the same because different representation merely reorganize the weights. Thus, we can pick an arbitrary representation in this step. However, the same is not true for the operator norm and we have to be a lot more careful in the next step. For each j ∈ [K +M ], we have ‖Wj(t)‖2F − ‖Fin(t)‖2F = D0, (70) where D0 = ‖Wj(0)‖2F − ‖Fin(0)‖2F fixed at initialization. Now, similar to the proof of Theorem 1, we bound the difference between the operator norm ofWj(t) and Fin(t) by a telescoping argument. By Lemma 10, switching from one matrix representation to the other for ResNet incurs at most a multiplicative factor of 8 and an additive factor cost that depends only on the initialization. In each adjacent layer, the maximum number of switch between representation is one (so that it fits the form prescribed in Theorem 1). By matrix invariance between adjacent layers of the K +M pairs of adjacent layers,
‖Wl(t)‖22 ≥ C‖Wl+1(t)‖22 −Dl, (71)
for C = 1/8 if the k + 1 layer is a ResNetFree block (Lemma 10), C = 1/min(ak+1, bk+1) if the k + 1 layer is a convolutional layer, C = maxdimW [M+1] if k = M (Lemma 9) and C = 1 otherwise; for Dl = ‖W>l+1(0)Wl+1(0)−Wl(0)W>l (0)‖22. Telescope the sum and subtract from 70 to get the statement of the theorem. When Frobenius norm diverges, divide both sides by the Frobenius norm to get the ratio statement. Note that the bound ‖W‖2F /rank(W ) ≤ ‖W‖22 is trivial since the largest singular value squared is at least the average singular value squared.
When the lower bound of 14 is 1, it matches the upper bound and thus the largest singular value dominates all other singular values. Alignment follows from the proof of Lemma 2.6 second point in Ji & Telgarsky (2019).

heading: E PROOF OF COROLLARY 1
text: Proof. Let L be the number of layers in the network. Under the conditions stated in Corollary 1, Lyu & Li (2020) and Ji & Telgarsky (2020) showed that ‖w(t)‖2 diverges. Invoke Lemma 4 for all k ∈ [L − 1] and sum up the results, we have L‖WL(t)‖2F = D′′ + ∑L j=1 ‖Wj(t)‖2F ‖Wk‖2F = D′′+ ‖w(t)‖22 where D′′ is constant in t. Thus ‖Wj(t)‖2F diverges for all j ∈ [L]. Since the sum of all but the largest singular value is bounded, but the sum of all singular values diverge, we conclude that the largest singular value eventually dominates the remaining singular values. Together with convergence in direction for these architecture Ji & Telgarsky (2020), we have each matrix converges to its rank-1 approximation.
That all the feedforward neural networks with ReLU/leaky ReLU/linear activations can be definable in the same o-minimal structure that contains the exponential function follows from the work of Ji & Telgarsky (2020) and that definability is closed under function composition.

heading: F EXTENSION TO GRADIENT DESCENT
text: Recall that with gradient descent for some step size η : N→ R≥0, the weight trajectory is a solution to the system of finite differences:
w(t+ 1)− w(t) = −η(t)d(w(t)), (72)
for some {d(w(t)) ∈ ∂R(w(t))}t∈N sequence of subgradient choice at each time step. This section essentially recovers Ji & Telgarsky (2019) extension of deep linear network results to gradient descent.
From 72, for some {d(w(t)) ∈ ∂R(w(t))}t∈N, we have,
w(t+ 1)w(t)− w(t)2 = −η(t)w(t)d(w(t)) (73) w(t+ 1)2 + w(t)2 − 2w(t+ 1)w(t) = η(t)2d(w(t))2, (74)
by multiplying both sides with w(t) or squaring both sides respectively.
Combine the above two equations to get:
w(t+ 1)2 − w(t)2 − η(t)2d(w(t))2 = −2η(t)w(t)d(w(t)). (75)
Take a telescoping sum to get:
w(t+ 1)2 − w(0)2 − t∑
τ=0
η(τ)2d(w(τ))2 = −2 t∑
τ=0
η(τ)w(τ)d(w(τ)). (76)
Fix an edge e and recall that we had from the proof of Theorem 1 that, for all s ∈ N,
we(s)[d(w(s))]e = ∑
p∈P|e∈p
1
n n∑ j=1 dj,p(w(s)). (77)
Therefore, fix a vertex v satisfying the conditions in Theorem 1, we have,∑ u∈INv wuv(t+ 1) 2 − wuv(0)2 − t∑ τ=0 η(τ)2[d(w(τ))]2uv (78)
=− 2 t∑
τ=0
η(τ) ∑
p∈P|v∈p
1
n n∑ j=1 dj,p(w(τ)) (79)
= ∑ b∈INv wvb(t+ 1) 2 − wvb(0)2 − t∑ τ=0 η(τ)2[d(w(τ))]2vb. (80)
which recovers a vertex-wise invariance with some slack terms. With an identical argument, we can recover the second part of Theorem 1 as well:∑
a∈IN wav(t+ 1)wau(t+ 1)− wav(0)wau(0)− t∑ τ=0 η(τ)2[d(w(τ))]av[d(w(τ))]au (81)
=− 2 t∑
τ=0 η(τ) ∑ a∈IN wav(τ)[d(w(τ))]au + wau(τ)[d(w(τ))]av (82)
=− 2 t∑
τ=0 η(τ) ∑ p∈A 1 n n∑ j=1 dj,p(w(τ)) (83)
=− 2 t∑
τ=0 η(τ) ∑ b∈OUT wvb(τ)[d(w(τ))]ub + wub(τ)[d(w(τ))]bv (84)
= ∑ b∈INv wvb(t+ 1)wub(t+ 1)− wvb(0)wub(0)− t∑ τ=0 η(τ)2[d(w(τ))]vb[d(w(τ))]ub. (85)
We thus recover the matrix invariance of Ji & Telgarsky (2019) equation C.9.
To control singular values of adjacent layers’ matrix representations, we needs to control the growth of the slack term using the step size η. One way to do this is to adaptively set the step size based on the Frobenius norm of each layer. Let us assume that at time step t, the maximum Frobenius norm of any layer is R(t) and that the risk R (as a function of time) has β(t)-Lipschitz gradient (or is β(t)-
smooth) in this Frobenius norm ball. Then by smoothness ofR, setting η(τ) = min ( 1, 1
β(τ)
) for
any τ ∈ N, we have,
R(w(τ))−R(w(τ + 1)) ≤ 〈 d(w(τ)),−η(t)d(w(τ)) 〉 + β(τ)η(τ)2
2 ‖d(w(τ))‖22 (86)
= −η(τ) 2 ‖d(w(τ))‖22. (87)
Therefore,
R(w(0)) ≤ R(w(0))−R(w(t+ 1)) ≤ −1 2 t∑ τ=0 η(τ)‖d(w(τ))‖22 (88)
≤ −1 2 t∑ τ=0 η(τ)2‖d(w(τ))‖22 (89)
≤ −1 2 t∑ τ=0 η(τ)2[d(w(τ))]e[d(w(τ))]f . (90)
for any e, f ∈ E. Therefore we conclude that the slack term is bounded by a quantity that is fixed at initialization. This allows us to recover Theorem 2 and Corollary 1 for gradient descent (but note that here we have an extra assumption in term of the smoothness of the risk function).

Review summaries:
This paper studies the invariance in training nonlinear networks under gradient flow or differential inclusion. It is shown that, for various network architectures, there are time-invariant quantities related to networks weights, if the trajectory is in the sign-stable regime (the sign of the weights does not change). This sign-stable regime invariance suggests the weight matrices are necessarily low-rank, provided that they diverge to infinity along some non-degenerate directions. 

This paper studies the low-rank phenomena in the context of *non*linear neural networks. In this work, the authors prove, via a tree network transformation of their initial network, that there exists some matrix invariance across consecutive layers  (thm 1). Their assumptions are relatively mild (except maybe Assumption 1 that I discuss in my main review)  They then leverage that invariance results in order to show a low-rank phenomenon (thm 2) for a wide range of neural networks with positively-1-homogeneous activation functions. 

The paper shows under certain assumptions, there exist invariants in DNNs with ReLU (or leaky ReLU and identity) activations - similar to the invariants observed in linear networks. To show this invariance a decomposition of the DNN as the composition of a multilinear function and a network with {+1,-1} weights. Using these invariants they show that for linearly separable data, the absolute value of the weight matrices converge to rank one matrices (assuming directional convergence).