{'fraction_non_alphanumeric': 0.04702743125191203, 'fraction_numerical': 0.013307726299330365, 'mean_word_length': 3.943207594724019, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Training invariances and the low-rank phenomenon: beyond linear networks

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 last few linear layers of the much wider class of nonlinear ReLU-activated feedforward networks containing fully-connected layers and skip connections. Similar to the linear case, the proof relies on specific local training invariances, sometimes referred to as alignment, which we show to hold for submatrices where neurons are stably-activated in all training examples, and it reflects empirical results in the literature. We also show this is not true in general for the full matrix of ReLU fully-connected layers. 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.

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 ResNet, 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, 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 or submatrices. Second, we argue that a matrix-wise invariance is not always true for general ReLU fully-connected layers. Third, we obtain low-rank results for arbitrary non-homogeneous networks whose last few layers contain linear fully-connected and linear 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 1). 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. Via these invariances, we prove that for architectures containing fully-connected layers, convolutional layers and residual blocks, when appropriately organized into matrices, adjacent matrices or submatrices of neurons with stable activation pattern have bounded singular value (Theorem 1).
• In the stable sign regime, we show a low-rank bias for arbitrary nonhomogeneous feedforward networks whose last few layers are a composition of linear fully-connected and linear ResNet variant 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 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 feedforward networks with positively-homogeneous activation (e.g., ReLU) to a multilinear structure (Lemma 1).

RELATED WORKS
Decomposition of fully-connected neural networks into a multilinear part and a 0-1 part has been used by Choromanska et al. (2015); Kawaguchi (2016), but their formulation does not apply to 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 network that Khim & Loh (2019) use to analyze generalization of fully-connected networks. We describe their approach in Section 2 and show how we extend their construction to arbitrary feedforward networks. 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 ( (2021) gives explicit close form optimal solution, which is both low rank and aligned, for the regularized objective. This was done for both the linear and ReLU neural networks. In our work, we focus on the properties of the network along the gradient flow trajectory.

PRELIMINARIES AND NOTATION
For an integer k ∈ N, we write the set [k] := {1, 2, . . . , k}. For vectors, we extend the sign function sgn : . For some (usually the canonical) basis (e i ) i∈ [n] in some vector space R n , for all x ∈ R n we use the notation [x] i = x, e i to denote the i-th coordinate of x.
The Clarke subdifferential generalizes both the smooth derivative when f ∈ C 1 (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. We do not delve in too much depth into Clarke subdifferentials in this paper, but use it when we extend previous results that also use this framework. We refer to e.g. (Davis et al., 2020;Ji & Telgarsky, 2020;Bolte & Pauwels, 2020) for more details. Each neuron v ∈ V \I is equipped with a positively 1-homogeneous activation function σ v (such as the ReLU x → max(x, 0), leaky ReLU x → max(x, αx) for some small positive α , or the linear activation).
To avoid unnecessary brackets, we write w e := w(e) for some e ∈ E. We will also write w ∈ R E , 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 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 := p 1 , . . . , p ρ be the enumeration of these paths. For a path p ∈ P and an input x to the neural network, denote by x p the coordinate of x used in p.

Given a binary classification dataset
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.
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 a partition of Definition 3 (Tree networks). A feedforward network ν with graph G is a tree network if the underlying undirected graph G is a tree (undirected acyclic graph). ResNet (He et al., 2016), DenseNet (Huang et al., 2017), CNNs (Fukushima, 1980LeCun et al., 2015) and other fully-connected ReLU architectures.

Examples of feedforwards networks include
For a fully-connected network ν with layer partition V =: V 1 . . . V L+1 where L is the number of (hidden) layers, let n i := |V i | be the number of neurons in the i-th layer and enumerate V i = {v i,j } j∈ [ni] . Weights in this architecture can be organized into matrices W [1] , W [2] , . . . , W [L] where Most practical architectures are not tree networks, but trees have been used to prove generalization bounds for adversarial risk.
In particular, for fullyconnected neural networks f whose activations are monotonically increasing and 1-Lipschitz, Khim & Loh (2019) define the tree transform as the tree network T f ( p3,p2 σ w p2..p L + n1 p1=1 W [1] p2,p1 x p1 for vectors w with L j=2 n j entries, indexed by an L-tuple (p 2 , . . . , p L ). We extend this idea in the next section.

STRUCTURAL LEMMA: DECOMPOSITION OF DEEP NETWORKS
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 = p 1 , . . . , p ρ . The path enumeration function h is defined for this network as We first state the main result of this section, proven in Appendix B. Lemma 1 (Decomposition). Let ν : R d → R be a feedforward network with computation graph G, and ρ the number of distinct maximal paths in G. Then there exists a tree network µ : R ρ → R such that ν = µ • h where h : R d → 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: where Z p (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 of Z p on numerical values of w. 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 w e (when it exists) between the two approaches, in the limit where weight signs are constant: (using Z p in Eqn. 1) ∂ν/∂w e = p∈P|e∈p w e ∂Z p (x; w)/∂w e + Z p (x; w) In particular, the dependence of Equation 2 on w e is extremely simple. The utility 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 first done on vertices closest to the output vertex (in number of edges on the unique path between any two vertices in a tree) and continues 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 Appendix A.

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

STABLE SIGN REGIME: A CONSEQUENCE OF DIRECTIONAL CONVERGENCE
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 t 0 < t N ∈ [0, ∞], we assume that for all t ∈ [t 0 , t N ), sgn(w(t)) = sgn(w(t 0 )). If this holds, we say that gradient flow is in a stable sign regime. Without loss of generality, when using this assumption, we identify t 0 with 0 and write "for some t ≥ 0" to mean "for some t ∈ [t 0 , t N )".
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, w e = 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) for the exponential/logistic loss and 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. lim t→∞ 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 the behavior is (multi)linear. In contrast, directional convergence of the weights does not imply such a reduction from the ReLU-activation to the linear case. Similarly, with stable signs, the parts of the input where the network is linear are not convex, as opposed to the linearized case (Hanin & Rolnick, 2019) (see also Claim 2).
Stable sign implication. The motivation for Assumption 1 is that weights in the tree network µ in Lemma 1 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 w e in each entry of h is at most 1 by definition of a path; and if ν is fully-connected, then h is a R n1×n2×...×n L tensor.

TRAINING INVARIANCES
First, we state an assumption on the loss function that holds for most losses used in practice, such as the logistic, exponential or squared loss. Assumption 3 (Differentiable loss). The loss function : R → R is differentiable everywhere. Lemma 2 (Vertex-wise invariance). Under Assumptions 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, and v have the same activation pattern (preactivation has the same sign) for each training example and for a.e time t ≥ 0, then for a.e. time t ≥ 0, In particular, the authors showed that the difference between incoming and outgoing weights does not change. Invoking the Fundamental Theorem of Calculus (FTC) over this statement will return ours. However, their proof may not hold on a nonnegligible set of time t due to the use of the operational chain rule that holds only for almost all w e . 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 2 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 ResNetIdentity is the most common version of ResNet in practice. ResNetIdentity is a special case of ResNetDiagonal, which is a special case of ResNetFree. Yet, theorems for ResNetFree do not generalize trivially to the remaining variants, due to the restriction of Lemma 2 and Lemma 3 to vertices adjacent to all learnable weights and layers containing all learnable weights. For readability, we introduce the following notation: Definition 6 (Submatrices of active neurons). Fix some time t, let W ∈ R a×b be a weight matrix from some set of a neurons to another set of b neurons. Let I active ⊆ [b] be the set of b neurons that are active (linear or ReLU with nonnegative preactivation). We write [W W ] active ∈ R |Iactive|×|Iactive| for the submatrix of W W with rows and columns from I active . Similarly, if W ∈ b × c is another weight matrix from the same set of b neurons to another set of c neurons then [W W ] active is defined as the submatrix with rows and columns from I active .
When applying Lemma 2 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 R a×b×c . Under Assumptions 1 and 3, we have the following matrix-wise invariance for a.e. time t ≥ 0: 1. (Fully-connected layers) W 1 ∈ R b×a and W 2 ∈ R c×b consecutive fully-connected layers, 2. (Convolutional layers) W 1 is convolutional, viewed as a flattening to a matrix R c×(a×b) , and W 2 adjacent convolutional, viewed as a flattening to a matrix R (d×e)×c ,

(Within residual block of ResNet
is a residual block of ResNetIdentity, ResNetDiagonal or ResNetFree,

(Between residual blocks of ResNet
j ∈ {1, 2} are consecutive ResNetFree blocks, 5. (Convolutional-fully-connected layers) W 1 convolutional, viewed as a flattening to a matrix R c×(a×b) and W 2 adjacent fully-connected layer, viewed as an rearrangement to R d×c , 6. (Convolutional-ResNetFree block) W 1 convolutional, viewed as a flattening to a matrix R c×(a×b) and W 2 is a rearrangement of U Z into an element of R d×c , where r(x; U, Y, Z) is an adjacent ResNetFree block, 7. (ResNetFree block-fully-connected layers and vice versa) 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).
Significance of Theorem 1. If we have a set of neurons that is active throughout training (which is vacuously true for linear layers), we can invoke an FTC and get for the submatrix restricted to these neurons. Assume for simplicity that the right hand side is 0, then the singular values of W 1 and W 2 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 2, we demonstrate the proof for the first point. The remaining points admit the exact same proof technique but on different matrices, which require some bookkeeping. Let W 1 ∈ R b×a and W 2 ∈ R c×b be two consecutive fully-connected layers for some a, b, c ∈ N number of vertices in these layers. Applying Equation 4 of Lemma 2 to each of the b shared neurons between these two layers, one obtains 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 to get the off-diagonal entries of Equation 6.
Next, we define layers for architectures where weights are not necessarily organized into matrices, e.g., ResNet or DenseNet. Definition 7 (Layer). Let F ⊂ E be such that 1) for all e = 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 3 (Edge-wise invariance). Under Assumptions 1 and 3, for all layers F and F that contain all learnable weights, it holds that for a.e. time t ≥ 0, Significance of Lemma 3. 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. The 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.

PROOF SKETCH OF LEMMA 2 AND LEMMA 3
The proofs of Lemma 2, Lemma 3 and Theorem 1 share the technique of double counting paths, which we explain next. For simplicity, we assume here 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 was used in (Arora et al., 2018) and involves simply writing down the partial derivative of the risk. We have, for some particular weight w e , e ∈ E, via the smooth chain rule where in the second line, we invoke the decomposition Lemma 1 and emphasize that µ has no learnable parameters in the stable sign regime. Now multiply w e to the above expression to get where does not depend explicitly on the edge e, with respect to which we are differentiating (only through w). Thus, we sum over in-edges and out-edges of a particular v satisfying the assumption of Lemma 2 to get Note that the only difference between Equations 10 and 11 is the set of paths that we are summing over, and we double count this set of paths. We use the definition of gradient flow to obtain ∂R(w)/∂w e = dw e (t)/dt and integrate with respect to time using a FTC to get the first part of Lemma 2. More work is needed to get the second part of Lemma 2, which is detailed in Appendix C. Finally, to get Lemma 3, we double count the set of all paths P.

NONINVARIANCE OF GENERAL RELU LAYERS
The restriction of Theorem 1 to submatrices of active neurons may appear limiting, but does not extend to the general case. With the same technique as above, we can write down the gradient for the Gram matrix W 1 W 1 for ReLU layers and show that it is not equal to its counterpart W 2 W 2 , thus giving a negative result: Lemma 4 (Noninvariance in ReLU layers). Even under Assumptions 3 and 1, for a.e. time t ≥ 0, for the different pairs of W 1 , W 2 detailed in Theorem 1.
Despite the negative result, the closed form of the gradient for the Gram matrices can be shown to be low rank with another subgradient model. Details may be found in Appendix C.

NONHOMOGENEOUS DEEP FEEDFORWARD NET
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 fully-connected network analogue has been known for some time. In light of Theorem 1, we define a matrix representation of a layer: Definition 8 (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 ∈ R a×b×c convolutional tensor it is the flattening to an element of R a×(b×c) ; and for a fully-connected layer it is the weight matrix itself.
Theorem 2 (Reduced alignment for non-homogeneous networks). Under Assumptions 1 and 3, let ν consist of an arbitrary feedforward neural network η, followed by K ≥ 0 linear convolutional layers (T a k ,b k ,c k ) k∈ [K] , followed by M ≥ 0 layers that are either linear ResNetFree blocks or linear fullyconnected layers; and finally ending with a linear fully-connected layer F in. For j ∈ [K + M ], denote by W [j] the matrix representation of the j-th layer after η, N r (j) the number of ResNetFree blocks between j and F in exclusively and V c (j) : Then there exists a constant D ≥ 0 fixed at initialization such that for a.e. time t > 0, Furthermore, assume that In particular, for the last few fully-connected layers j with N r (j) = 0 and V c (j) = 1, we have: where u j and v j are the left and right principal singular vectors of W [j] . Corollary 1. For fully-connected networks with ReLU activations where the last K layers are linear layers, trained with linearly separable data under logistic loss , under the assumptions that R(w(0)) < (0) and the limiting direction of weight vector (which exists (Ji & Telgarsky, 2020)) has no 0 entries, Equation 15 holds for the last K layers.
Significance Equation 13 and its limiting counterpart Equation 14 quantify a low-rank phenomenon by providing a lower bound on the ratio of the largest squared singular value (the operator norm) and the sum of all squared singular values (the Frobenius norm). This lower bound depends on the number (not dimensions) of ResNetFree layers (N r ) and certain dimensions of convolutional layers (V c ). When the dimensions of ResNetFree layers are large, max dim W [M +1] is small and the 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.

CONCLUDING REMARKS AND FUTURE DIRECTIONS
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 network. 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 the stable sign regime for a wider set of 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 A ILLUSTRATION OF LEMMA 1 We give a quick illustration of the two steps described in Section 3 for a fully-connected ReLUactivated network with 1 hidden layer. Figure 1 describes the unrolling of the neural network ( Figure  1a) into a tree network (Figure 1b). Figure 2a describes the weight pull-back in the hidden layer and Figure 2b describes the weight pull-back in the input layer. It is clear that the inputs of the tree net in Figure 2b are coordinates of the path enumeration function h(x; w) in this example. Furthermore, weights in the tree net depend entirely on the signs of the original weights. The rest of the proof argues this intuition for general feed-forward neural nets. As a remark, in general, ρ is a very large number -exponential in the number of layers for a fully-connected net with fixed width.    Figure 2: Pulling back of weights in a tree net. All nodes apart from the input nodes use the ReLU activation. The original net was drawn in Figure 1a and 1b. This is possible due to the positive-homogeneity of the activation function. From Figure 2b, one can recover the final tree net in Theorem 1 with weights from {−1, +1} and input from the path enumeration function h of the neural net by subdividing the edge incident to the input neurons and assign weights corresponding to sgn(h(x)).

B PROOF OF LEMMA 1
We first prove an absolute-valued version of Lemma 1 and show that the extension to Lemma 1 is straightforward. In other words, we first prove Lemma 5 (Absolute-valued decomposition). For an arbitrary feed-forward neural network ν : R d → R, there exists a tree network µ : R ρ → R such that ν = µ • h where h is the absolute-valued path enumeration function defined as h (x) = x p e∈p |w e | 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 ν : to be the set of input node of G and O G = {o G } to be the set of the single output node of G.
• P G to be the enumeration of all paths from any input node in I G to the output node o G .
• H G to be the enumeration of all paths from any node v ∈ G[V ] to the output node o G .
Note that if G has more than 2 vertices then H G ⊃ P G . • 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: and a post-activation function defined as Note that POST o G = ν. • v G p , e G p to be the vertex and edge, respectively, furthest from o G on some path p of G. • x G p to be the unique x j such that i G j ∈ p. Definition 9 (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 10 (Unrolling of feedforward neural networks). The unrolled tree neural network τ G of G is a tree neural network with computation graph T G where

• Unweighted graph (T G [V ], T G [E]) = HASSE(H G ). In particular T G [V ] = H G and we
identify vertices of T G with paths in G.
. Lemma 6 (Unrolled network computes the same function). Fix an arbitrary feedforward neural network ν : R d → R with computation graph G. Let τ G be the unrolled tree network of G with computation graph T G . Then ν = τ G .
Proof. We proceed with induction on α G := max p∈P |p| the longest path between any input node and the output node of G. In the base case, set α G = 0. Then V G = {o G } is a singleton and the neural network ν computes the activation of the input and return it. H G = V T = {p 0 } 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 p 0 in T , by construction, is the activation of o G . 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 .

Then showing that T G = G by constructing an isomorphism
that preserves E, w and σ.
The construction of G An illustration of the following steps can be found in Figure 3. Recall 1. Create m distinct, identical copies of G: G 1 , . . . , G m .

For each j ∈ [m]
, remove from G j all vertices u (and their adjacent edges) such that there are no directed path from u to v j .
3. We now note that α Gj ≤ t − 1 (to be argued) and invoke inductive hypothesis over G j to get an unrolled tree network τ j with graph T j such that τ j = ν j where ν j is the neural network computed by G j .
4. Finally, construct G by creating a new output vertex o G and connect it to the output vertices o Tj for all j ∈ [m]. As a sanity check, since each T j is a tree network, so is G . More precisely, Figure 3: Construction of G . G 1 and G 2 are the modified copies of G in step 2. In step 3, the transformation T Gi happens to coincide with G i for i = 1, 2 in this case. G is created in step 4 by adding an extra vertex o G and connecting it to v 1 and v 2 with the appropriate weights and activation and can be seen in Figure 1b. . G is well-defined We verify each steps in the above construction: 1. This step is well-defined.
2. For any G j , as long as α G ≥ 2 (by definition), we always remove o G from each G j in each step; since v j is an in-vertex of o G and G is a DAG. Otherwise, this step is well-defined.

Fix a j ∈ [m]. By construction (and since we always remove
, the path p * ∪ {o G } created by appending o G 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 where we invoked the inductive hypothesis in the last line to get and the rest are definitions.
G is isomorphic to T G Although this should be straightforward from the construction, we give a formal proof. Consider the isomorphism π : where paths are viewed as set of vertices. The second case is well-defined since p ∪ {o G } ∈ H G for any p ∈ H Gj for any j ∈ [m] by construction of G j .
We can now verify that π is an isomorphism between the two structures. Fix pq ∈ G [E]. Consider two separate cases: pq ∈ T j [E] for some j and pq ∈ T j [E] for any j. In the first case, by definition of T j as a Hasse diagram, p = {v p } ∪ q are paths in H Gj . Thus, π(p)π(q) = (p ∪ {o G })(q ∪ {o G }) satisfying π(p) = {v p } ∪ π(q). Thus, by definition of Hasse diagram, π(p)π(q) ∈ T G [E]. Furthermore, G [w](pq) = G[w](e p ) = T G [w](π(p)π(q)) In the second case, we have pq . Then by definition, 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 ν : 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. Iteratively apply Lemma 7 to vertex π 1 , . . . , π ξ in T G while maintaining the same function. After ξ such applications, we arrive at a network µ G with graph M G 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 o T G . Therefore, at iteration j, ; otherwise, π j is an input vertex corresponding to input x πj , then x πj is modified to This completes the proof.
Now we present the extension to Lemma 1: Proof of Lemma 1. 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 i j ) 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 i p is a particular input neuron of µ in the decomposition lemma (Lemma 1). Since µ is a tree neural network, we there exists a distinct node u p in µ that is adjacent to i p . Remove the edge i p u p , add a neuron u p , connect i p u p and u p u p , where the weight of the former neuron is set to sgn e∈p w e and the latter to w[µ ](i p u p ). 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.

C PROOF OF TRAINING INVARIANCES
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 min i |v i |/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 function w : R → R d such that w(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 ∈ R d . Consider the function t → v|t sin(t)|.
Lemma 8 (Clarke partial subderivatives of inputs with the same activation pattern is the same). Assume stable sign regime (Assumption 1). Let p 1 , p 2 ∈ P be paths of the same length L. Let p 1 = {v 1 , . . . , v L } ∈ V L and p 2 = {u 1 , . . . , u L } ∈ V L . Assume that for each i ∈ [L], we have v i and u i having the same activation pattern for each input training example, where the activation of a neuron is 0 if it is ReLU activated and has negative preactivation; and is 1 if it is linearly activated or has nonnegative preactivation. Then ∂ p1 µ(h) = ∂ p2 µ(h) where ∂ is the Clarke subdifferential.
Proof. In this proof, we use the absolute-valued version of the decomposition lemma. Fix a training example j and some weight w 0 and let the output of the path enumeration function be h := (h p = h(x j ; w 0 )) p∈P . Denote X ⊆ R 2 the input space of all possible pairs of values of (p 1 , p 2 ) such that Assumption 1 and the extra assumption that both paths have the same activation pattern on each neuron hold. Let m : R 2 → R be the same function as the tree network µ but with all but the two inputs at p 1 , p 2 frozen. We will show that m is symmetric in its input. Once this is establish, it is trivial to invoke the definition of the Clarke subdifferential to obtain the conclusion of the lemma.
Let (a, b) ∈ X ⊆ R 2 . We thus show that if (b, a) ∈ X then m(a, b) = m(b, a). Recall that µ is itself a ReLU-activated (in places where the corresponding original neurons are ReLU-activated) neural network. The fact that µ has a tree architecture means that for each input node, there is a unique path going to the output node. Thus, the set of paths from some input node in µ to its output node can be identified with the set of inputs itself: P. Now let us considered the product of weights on some arbitrary path p. It is not hard to see that for each such path, the product is just P p = e∈p w e since the input to p is |P | and going along the path collects all signs of w e for all e ∈ p.
We now invoke the 0-1 form of ReLU neural network to get m(a, b) = µ(h) = p∈P Z p (a, b)P p (a, b) where Z p is 1 iff all neurons on path p is active in the µ network (recall that we identify paths in µ to input nodes). Consider that what changes between m(a, b) and m(b, a): since µ is a tree network, exchanging two inputs can only have effect on the activation pattern of neurons along the two paths from these inputs. However, we restricted X to be the space where activation pattern of each neuron in the two paths is identical to one another. Since both (a, b) and (b, a) is in X , swapping one for another does not affect the activation pattern of each neuron in the two paths! These neurons activation pattern is then identical to those in network µ by construction and hence Z p (a, b) = Z p (b, a) for all p ∈ P since activation pattern of each node of the µ network stays the same. Thus we conclude that m(a, b) = m(b, a). This completes the proof.
Proof of Lemma 2. This proof uses the absolute-value-free version of the decomposition lemma. This is just to declutter notations, as the same conclusion can also be reach using the other version, with some keeping track of weight signs. 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 w e (t) is also absolutely continuous for any e ∈ E. For absolutely continuous functions w e (t) for some e ∈ E, invoke the Fundamental Theorem of Calculus (FTC) (Chapter 6, (Heil, 2019)), to get: We now proceed to compute dw dt (s). Since w(t) is absolutely continuous and we are taking the integral via FTC, we only need to compute dw dt (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 (g j ) n j=1 such that g j ∈ ∂ν xj (w) ⊆ R |E| for all j ∈ [n] where ν xj (w) = ν(x j ; w), and for a.e. time s ≥ 0, dw dt (s) = 1 n n j=1 l (y j ν(x j ; w(s))) · y j · g j Fix j ∈ [n], by the inclusion chain rule, since ν xj = µ • h xj , with h and µ also locally Lipschitz, we have by Theorem I.1 of Lyu & Li (2020), Thus there exists (γ a ) A a=1 ≥ 0, A a=1 γ a = 1 and (α a ∈ ∂µ(h(w)), β a j,p ∈ ∂[h xj ] p (w)) A a=1 such that: Here we use Assumption 1 to deduce that eventually, all weights are non-zero in gradient flow trajectory to compute: Plug this back into g j to get: Plug this back into dw dt (s) and to get, coordinate-wise, for a.e. s ≥ 0, Multiply both sides with w e gives: where Note that d does not depend on the specific edge e used in Equation 33 and also that the term given by β does not depend on a and we can simply write α p for A a=1 γ a [α] a p . Plugging back into the FTC to get: Finally, by an identical argument but applied to the set of edges vb for some b ∈ OUT v , we have: 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 IN v = IN u = IN and OUT v = OUT u = OUT with stable activation pattern for each training example. To make it more readable, we drop the explicit dependence on t in our notation and introduce some new ones: for some a ∈ IN, let P I→a be the set of all paths from some input node in I to node a and for some b ∈ OUT, let P b→o be the set of all paths from b to the output node o. Then one can decompose the sum as where α p is the partial Clarke subdifferential at input p.
Recall that the end goal is to derive Using equation equation 40, the second term on the right hand side becomes where the product w av · f ∈p1∪p2 ·w f w ub is a jagged path. Then one continues with the derivation to get On the other hand This is where the more restrictive assumption that for each training example, u and v have the same activation pattern as each other (but the same activation pattern between u and v of, say x 1 , may differs from that on, say x 2 ). Under this assumption, we can invoke Lemma 8 to get α p1∪{u}∪p2 (x j ; w) = α p1∪{v}∪p2 (x j ; w) as a set. This identifies 46 with 49 and gives us: This holds for any time t where u and v has the same activation pattern. If further, they have the same activation pattern throughout the training phase being considered, then one can invoke FTC to get the second conclusion of Lemma 2. Note, however, that we will be using this differential version in the proof of Theorem 1.
Proof of Lemma 3. The proof is identical to that of Lemma 2, 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 7), 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 2) for a.e. time s ≥ 0, for any layer F .
Before continuing with the proof of Theorem 1, we state a classification of neurons in a convolutional layer. Recall that all convolutional layers in this paper is linear. 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 11 (Convolutional tensors). Free parameters in a (bias-free) convolutional layer can be organized into a tensor T ∈ R a×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 12 (Convolutional neuron organization). Fix a convolutional layer with free parameters T ∈ R c×b×a . Then neurons in this layer can be organized into a two dimensional array {v j,k } j∈[l],k∈[c] for some l ∈ N such that 1. For all j, j ∈ [l] and for all k ∈ [c], v j,k and v j ,k share all its input weights. More formally, there exists a bijection φ : for all u ∈ IN vj k .
2. For all j ∈ [l] and for all k, k ∈ [c], v j,k and v j,k has the same in-vertices and out-vertices. In other words, For example, in the first convolutional of AlexNet in R 96×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 9 (Extension of Lemma 2 to weight sharing). Let V := {v j,k } j∈[l],k∈{1,2} be a convolutional neuron organization. Recall that by definition 12, for all j ∈ [l], IN vj,1 = IN vj,2 =: IN j and OUT vj,1 = OUT vj,2 =: OUT j . We have for a.e. time t ≥ 0, where w IN (V) := {(w 1 , w 2 ) | ∀j ∈ [l], ∃a j ∈ IN j , w aj vj,1 ≡ w 1 and w aj vj,2 ≡ w 2 }, and similarly, 2} be consecutive ResNetFree block. Let Y 1 be fully connected from neurons V 1 to neurons V 2 , U 1 be fully-connected from V 2 to neurons V 3 , Y 2 be fully-connected from neurons V 3 to V 4 and U 2 be fully-connected from V 4 to neurons V 5 .
Invoke the first point to get the conclusion.
5. Let the convolutional tensor be T ∈ R c×b×a with convolutional neuron organization {v j,k } j∈[l],k∈[c] for some l ∈ N. Let the adjacent fully-connected layer be W ∈ R d×(l×c) . Form the matrix representation W 1 ∈ R c×ab and W 2 ∈ R dl×c as per the theorem statement. Then we have for any k, k ∈ [c] and for all j ∈ Invoke Lemma 9 to get the conclusion.
6. Let r(x; U, Y, Z) be a residual block of either ResNetIdentity, ResNetDiagonal or ResNet-Free. Let Y be fully-connected from neurons V 1 to neurons V 2 , U be fully-connected from neurons V 2 to neurons V 3 . Thus, Z is fully-connected from V 1 to V 3 . Then W 2 = U Z is fully connected from V 1 to V 2 ∪ V 3 .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 V 1 to V 2 and U fully connects V 2 to V 3 . Then we have U Z fully-connects V 1 ∪V 2 to V 3 . 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 V 3 to V 4 and U fully-connects V 4 to V 5 . Then Y Z fully-connects V 3 to V 4 ∪ V 5 and we one again invoke the first point to get the conclusion.
Proof of Lemma 4. This is the continuation of the proof of Lemma 2. To obtain noninvariance, one only needs to show that when u is active and v inactive, the expression in 46 and 49 are not equal in general. For the sake of notation, we pick the case where the preactivation of u is strictly positive, that of v is strictly negative, and further assume that the whole network is differentiable at the current weights w for all training examples.
In this case, it is not hard to see that the Clarke subdifferential ∂ w µ(h) is a singleton and contains the gradient of the µ network. Furthermore, for any path p = (v 1 , . . . , v L ), the partial derivative ∂µ ∂p is 1 if all neurons on p are active and 0 otherwise. Thus, we have We can actually factorize this even further by noticing that the term w av does not depend on b and w ub does not depend on a. Rearranging the sum and factorizes give: On the other hand Take, for example, an asymmetric case where the in-edges of v has much larger weights than that of u while out-edges of v has much smaller weights than that of u, then 65 is much larger than 67 and therefore the two expressions are not equal in the general case. A symmetric initialization scheme that prevents the above asymmetry may prevent this from happens, but this requires additional assumptions and is opened to future work.
Remark 1. Using the automatic differentiation framework while setting the gradient of ReLU to be 1 if the preactivation is nonnegative while 0 otherwise, the same derivation of 65 can be achieved. Interestingly, if one only has a single example, then the final expression of 65 implies that the matrix d dt W k W k has rank at most 2, where W k is a weight matrix in, for example, ReLU fully-connected neural network. Controlling the eigenvalues under low-rank updates may allow us to bound singular values of the full weight matrices W k . The resulting bound would not be uniform over time, but improves with training and is thus a different kind of low rank result. This, however, is outside of the scope of this paper.

D PROOF OF THEOREM 2
First we state a helper lemma Lemma 10 (Largest singular value of different flattening of the same tensor is close). Let T ∈ R a,b,c be an order 3 tensor (say a convolutional weight tensor). Let T 1 , T 2 be the standard flattening of this tensor into an element in R c×(a×b) and R (b×c)×a respectively. Then, = max(c, 0) · max(a, b) = c max(a, b).
Plug this in equation 69 to get the final result.
Lemma 11 (Shuffling layer in linear ResNetFree block preserves largest singular value up to multiple by 8). Recall that for a ResNetFree block r(U, Y, Z) with Y ∈ R b×a , U ∈ R c×b and Z ∈ R c×a , there are two possible rearrangement of the weights A = U Z and B = Y Z . We have Published as a conference paper at ICLR 2022 Proof. Recall that by point three of Theorem 1, we have matrix invariance Note that we can obtain this form since we are only considering linear ResNetFree blocks, so all neurons are active at all time for all training examples. Thus, we can invoke a FTC to get this form from the differential from in theorem 1.
By line B.2 in Ji & Telgarsky (2019), where D = U (0)U (0) − Y (0)Y (0) 2 2 is fixed at initialization. For positive semidefinite matrix X, denote λ(X) to be the function that returns the maximum eigenvalue of X. We have where 77 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; 79 is a consequence of 74 and 81 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 ], we first invoke Lemma 3 to bound the Frobenius norm of each of the final K + M + 1 layers (counting the last layer F in) via the last layer. Let W j 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 re-organize 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 where D 0 = W j (0) 2 F − F in(0) 2 F fixed at initialization. Now, we bound the difference between the operator norm of W j (t) and F in(t) by a telescoping argument. By Lemma 11, 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, W l (t) 2 2 ≥ C W l+1 (t) 2 2 − D l , for C = 1/8 if the k + 1 layer is a ResNetFree block (Lemma 11), C = 1/ min(a k+1 , b k+1 ) if the k + 1 layer is a convolutional layer, C = max dim W [M +1] if k = M (Lemma 10) and C = 1 otherwise; for D l = W l+1 (0)W l+1 (0) − W l (0)W l (0) 2 2 . Telescope the sum and subtract from 83 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 2 F /rank(W ) ≤ W 2 2 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).

E PROOF OF COROLLARY 1
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 3 for all k ∈ [L − 1] and sum up the results, we have L W L (t) 2 . 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.