Training invariances and the low-rank phenomenon: beyond linear networks
Authors: Thien Le
Stefanie Jegelka
Venue: ICLR 2022 Spotlight (2022)
Keywords: deep learning
nonsmooth analysis
Clarke subdifferential
implicit regularization
low rank bias
alignment
training invariance

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 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.

Published as a conference paper at ICLR 2022
TRAINING INVARIANCES AND THE LOW-RANK PHE- NOMENON: BEYOND LINEAR NETWORKS
Thien Le & Stefanie Jegelka Massachusetts Institute of Technology {thienle, stef j @mmi edu
ABSTRACT
The implicit bias induced by the training of neural networks has become topic of rigorous study. In the limit of gradient flow and gradient descent with appropriate step size, has been shown that when one trains deep linear network with logis- tic 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-activaan feedforward networks con- taining fully-connected layers and skip connections. Similar to the linear case, the proof relies specific local training invariances, sometimes referred to as align- ment, 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 lay- ers. Our proof relies on specific decomposition of the network into a multilinear function and another ReLU network whose weights are constant under a certain parameter directional convergence.
INTRODUCTION
Recently, great progress has been made in understanding the trajectory of gradient flow (GF) & Telgarsky 2019 20200 Lyu & Li (020)) gradient descent (GD) (Ji & Telgarsky 2019 Arora et al.. 2018 and stochastic gradient descent (SGD) (Neyshabur al., 2015 2017) 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 ReL.U fully-connected networks or ResNets are highly non- non-linear. This causes the underlying optimization problem (usually empirical risk min- imization) to be highly non-smooth (e.g. for ReLUs) and non-convex, necessitating special tools such the Clarke subdifferential (Clarke) 1983).
One of the many exciting results of this body 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.c., max-margn classifier (Ji & Telgarsky 2019). while a relaxed version is true for CNNs (Gunasekar 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 Frobenius norm as 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. (202I) 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-wist wise invariances for fully-comnected 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,

---

Published as a conference paper at ICLR 2022
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, take steps to addressing wider set of architectures and invariances. First, we show a class of vertex and edge-wise quantities that remain invariant during gradient flow train- ing. Applying these invariances to architectures containing fully connected, convolutional and resid- ual blocks, arranged appropriately, we obtain invariances of the singular values in adjacent (weight) matrices submatrices. Second, we argue that a matrix-wise invariance is not always true for gen- eral 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.] (02T) for ResNet and CNNs. They also include the squared loss used there, in addition to the exponential
logistic loss used in most theoretical low-rank results. Moreover, our Theorem giivvss an explanation for the "reduced alignment" phe- nomenon observed by Ji & Telgarsky (2019), where in experiments on AlexNet over CIFAR-10 R-10 the ratio |[W] [// [| 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, tecture into a multilinear function and a ReLU network with +1/-1 weights. This reduction holds in the stable sign regime, certain convergence setting of the parameters. This regime different from stable activations, and is implied, e.g., by directional convergence of the parameters to vector with non-zero entries (Lemmal) This construction may be of independent interest.
specific decomposition of arbitrary ReLU archi-
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 D
In the stable sign regime, show 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, 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 the first time this type of bias is shown for nonlinear, nonhomogeneous networks.
We prove our results via decomposition that reduces arbitrarily structured feedforward networks with
activation (e.g., ReI.U) to a multilinear structure (Leema
1.1 RELATED WORKS
Decomposition of fully-connected neural networks into 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 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 P 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 al.
give detailed comparison between their approach and ours.
2015) or its variants (Neyshabur et al. 2017).
For linear networks, low-rank bias is proven for separable data and exponential-taiie loss in Ji & Telgarsky (2019). Du et al. (2018) give certain vertex-wiss invariances for fully-connected ReLU networks and Frobenius norm difference invariances for CNNs. Compared to their results, ours are slightly stronger since prove that invariances hold for almost every time & on the gradient
2

---

Published as a conference paper at ICLR 2022
flow trajectory, thus allowing for the of a Fundamental Theorem of Calculus and downstream analysis. Morcover, 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 (019) to vector- valued neural networks. In our work, we only consider scalar-valued neural networks performing binary classification. For linearly inseparable but rank-1 or whitened data, recent line of work from Ergen & Pilanci (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.
2 PRELIMINARIES AND NOTATION
For an integer & E N, we write the set [k] := (1, kj. For vectors, we extend the sign function
sgm R + {-1.1} coordinate-wist as sgn : (x)) + (sgn(z;))ss(d)) For some (usually the canonical) basis (ei) in some vector space RR"", for all x E IR" we use the notation [xr] = (1r, es)
to denote the i-th coordinate of xz
Clarke subdifferential, definability and nonsmooth analysis. The analysis of non-smooth func- tions is central to our results. For locally Lipschitz function f D + I with open domain D, there exists a set D C D of full Lebesgue measure on which the derivative / exists everywhere by Rademacher's 's theorem. As a result, calculus can usually be done over the Clarke subdifferentia (x) == CONV (lim fzx))) x, E D + x} where CONV denotes the convex hull.
The Clarke subdifferential generalizes both the smooth derivative when f E C' (continuously dif- ferentiable) and the convex subdifferential when f is convex. However, it only admits chain rule with an inclusion and not equality, which is though necessary for backpropagation in deep learn- ing. 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.
Neural networks. Consider a neural network V : 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 E V. let IN, == {u E V uv E }} and OUT, == fw E V ew E }}} be the input and output neurons of v. Let {i,, 12.............. ................................ ia} =: I C V and O == fo} c V be the set of input and output neurons defined as (N) 0 (UT( Vi E T. Each neuron V is equipped with positively 1-homogeneous activation function a, (such as the ReLUU + max(x, 0), leaky ReLU x + max ax) for some small positive or the lincar activation).
To avoid unnecessary brackets, write w. = w(e) for some e E. We will also write w E R where F. is the set of learnable weights, the vector of learnable parameters. Let P be a path in G, i... a set of edges in E' that forms a path. We write v E P for some v E V if there exists E V such that uv E P or vu P. Let p be the number of distinct paths from any I E O. Let p== {pr.....Pe Pp} be the enumeration of these paths. For path p E P and an input x to the neural network, denote by xp the coordinate of x used in p.
Given a binary classification dataset { 9:) (E(M) with 2, Rdd || S and y {-1,1), we minimize the empirical risk R(w) Em (()v((x)) 1 Em= ((v(yer:) with loss é R
R. using gradient flow dwn(1) E - -0R(w(t)).
As we detail the architectures used in this paper, we recall that the activation of each neuron is still The networks considered here are assumed to be bias-free.
Definition 1 (Feedforward networks). A neural net v with graph G is a feedforward network if G is directed acyelic graph (DAG).
Definition 2 (Fully-connected networks). A feedforward network v with graph G is a fully-
connected network if there exists a partition of V into V (I = V)) V22 LV = 0) such that for all u E V, uv E E iff there exists E [L] such that u E V; and u E Vi+
Definition (Tree networks), A Afeedforward network v with graph G is a tree network if the under- lying undirected graph G is tree (undirected acyelic graph).
3

---

Published as a conference paper at ICLR 2022
Examples of feedforwards networks include ResNet (He al., 2016). DenseNet (Huang et al. 2017]. CNNs (Fukushima) 1980 LeCun et al. 2015) and other fullycoonnectdd ReLU architectures.
For fonneccod network with layer partition V =: V1 L. L UL+1 where L is the number of (hidden) layers, let n, := [V] be the number of neurons in the i-th layer and cnumerate V; = [u.sheepo.) Weights in this architecture can be organized into matrices Will, W W where R 3 Wlll = ((Wo,,"e-1..)) (nt for all E [Z]-
Tree networks. Most practical architectures are not tree networks, but trees have been used to prove generalization bounds for adversarial risk. In particular, for fully- connected neural networks [ whose activations are monotonically increasing and 1- Lipschitz, Khim & Loh (2019) define the Iree transform as the tree network [s(;;; (x) =
E
"pp.
Wps.p ...Ep=
(Up2-PL PL + Ep
W Pa-Pi Tp.)
for vectors w with
I ny entries, indexed by an L-tuple (P2,....PPL) We extend this idea in the next section.
STRUCTURAL LEMMA: DECOMPOSITION OF DEEP NETWORKS
We begin with decomposition of neural network into multilinear and non-weighted nonlinear part, which will greatly facilitate the chain rule that we need to apply in the analysis. Before stating the decomposition,
need the following definition of a path enumeration function, which computes the product of all weights and inputs on each path of neural network.
Definition 4 (Path enumeration function). Let be feedforward neural network with graph G and paths P {pI...... .Pp). The path enumeration function h is defined for this network as h: (I1, (21, ... Fa) Tp Ilep We)
where Fp == Iy such that E E.
PEP
We first state the main result of this section, proven Appendix B
Lemma (Decomposition)). Let v Red - R. be feedforward network with computation graph G, and p the number of distinct maximal paths in G. Then there exists tree network μ RR - such that p where h [g + Rº is the path enumeration function of G. Furthermore, all weights in y are either - or +1 and fully determined by the signs of the weights v.
Path activation of ReLU networks in the literature. The viewpoint that for every feedforward network y there exists a tree network μ such that v = 1 o is not new and our emphasis here is on the fact that the description of J IRP - IR 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 sum over paths:
vl:; w)
Σ PEP
2z(2: w
II we (<zp(x: PPP. ((: cEp
where (x; w) 1 iff all ReLUs on path p are active (have nonnegative preactivation) and otherwise. One can then take μ a tree network with no hidden layer, p input neurons all connected to a single output neuron. However, this formulation complicates analyses of gradient trajectories, because of the explicit dependence of Zp numerical values of w. In our lemma, f 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, l is fixed, allowing for 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 T.T. To this, compare the partial derivative with respect some w, (when it exists) between the two approaches, in the limit where weight signs are constant:
(using Lemma Db
0v/0w,-
Σ PEP
[Vmn(x;;)) w)]p I II wf,
(2)
/EP.J$e
(using Zp in Eqn. D
Ov/Owe
Σ
(1)
(x)
II Wy.
(3)
PEP eEP
fEP.f
In particular, the dependence of Equation 2 on w, is extremely simple. The utility of this fact will be made precise in the next section when we study invariances.
4

---

Published as a conference paper at ICLR 2022
Proof sketch. The proof contains two main steps. First, "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 fully-connected network; we generalize it to work with arbitrary feedforward networks. Second, "pull back" the weights towards the input nodes using positive homogeneity of the activations: a (z) = sgn(a) (r)aa) 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 ReL ueltivctiv network with hidden layer in Appendix A
4 MAIN THEOREM: TRAINING INVARIANCES
In this section, we put the previous decomposition lemma to use in proving an implicit regullaiztio property of gradient flow when training deep neural networks.
4.1 STABLE SIGN REGIME: A CONSEQUENCE OF DIRECTIONAL CONVERGENCE
Recall the gradient flow curve {w(())etfo.o)) defined by the differential inclusion dw)(() -R)(w(t). We first state the main assumption in this section.
di
Assumption 1 (Stable sign regime). For some to < iN E [0, oo], we assume that for all t e (to, t2), ) sggn((()) (w(t)) sgn( wto)) If this holds, we say that gradient flow is in stable sign regime. Without loss of generality, when using this assumption, we identify to with 0 and write "for some t 2 0" mean "for some E [to, IN)".
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- vanishiis limit in each entry). We assume that
w(t) t- w exists, is finite in each entry and furthermore, for all E, We + O. [[((]]
is straightforward to see that Assumption follows from As- sumption? 2 but we provide proof in the Appendix (Claim TT. Directional convergence was proven byDi & 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 archi- tectures. 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, weight that converges to 0 can change sign an infinite number of times).
Motivation and justification.
Pointwise convergence is too strong in general. Note also that assuming pointwise convergence of the weights (i.e. lim,-poc (t) exists and is finite) is a much stronger statement, which not true for the case of exponential/loiistee loss and homogeneous networks (since [lx((t)l22 diverges, see for example Lyu & Li (2020), Ji & Telgarsky (2020), Jī & Telgarsky| (2019)). Even when pointwise convergence holds, 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 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 Rettvacciin 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 I is that weights in the tree network in Lemma]] Tare are fully determined by the signs of the weights in the original feedforward network v. Thus, under Assumption] [] one can completely fix the weights of μ it has no learnable parameters. Since we have the decomposition v = f o where 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. in each entry of is most by definition of path; and if is fully-connected, then h is R X Xnz tensor.
5

---

Published as a conference paper at ICLR 2022
4.2 TRAINING INVARIANCES
First, we state an assumption on the loss function that holds for most losses used in practice, such as the logistic, exponential squared loss.
Assumption (Differentiable loss). The loss function & RR- + R differentiable everywhere.
Lemma (Vertex-wise invariance). Under Assumptions 7 and 3
for all v E VV(UUO)) such that all edges incident to v have learnable weights, for a.e. time
Σ uEIN'
w (t)
Σ
(t)
Σ WEIN'
w (0)
ob (0).
(4)
bEOUT,
bEOUT.
If we also have IN,, = IN, = IN and OUT, = OUT, OUT and u and have the same activation pattern (preactivation has the same sign) for each training example and for a.e time 2 0, then for a.e. time t 2 0.
Σ aEIN
Wau (to Σ Wab(t)ueb(t) = Σ
Wau (O)
Σ
Wab (0) (5)
BEOUT
aEIN
BEOUT
Comparison to Du et al. 2018 closely related form of Equation 4 in Lemma has appeared in Du et al. (218) (Theorem 2.1) for fully-connected ReLU//eaky-Redi ReelL networks. In particular, the authors showed that the difference between incoming and outgoing weights does not change. In- voking the Fundamental Theorem of Calculus (FTC) over this statement will return ours. However, their proof may not hold on nonnegligible set of time due to the use the operational chain rule that holds only for almost all w... Thus the FTC can fail. The stronger form showed here is useful in proving downstream algorithmic consequences, such as the low rank phenomenon. Furthermore, result also holds for arbitrary feedforward architectures and not just the fully fully-connected case.
Before we put Lemma 2 to use, we list definitions of some ResNet variants.
Definition 5. Denote ResNetldentity, ResNetDiagonnal and ResNetFree be the version of ResNet described in He et al. (2016) where the residual block is defined respectively as
1. r(;; U,Y) - o(oo(Y 1z) where IR, RR, YYU T E bxb aand 1 is the identity,
2. r(x U,Y. (Uoo(Yz) + Dx) where I E R2 Y.UT T Rbxa and D diagonal,
3. r(x; U,Y, = (UU((Yx) + Zx) where RA Rixa U Rexb and E Rx
ResNetldentity is the most common version of ResNet in practice. ResNetldentity is special case of ResNeeDiagonal, which a special case of ResNetFree. Yet, theorems for ResNetFree do not generalize trivially the remaining variants, due to the restriction of Lemma and Lemma 3 to vertices adjacent to all learnable weights and layers containing all learnable weights. For readability, introduce the following notation:
Definition 6 (Submatrices of active neurons). Fix some time I, let W E Raxb be a weight matrix from some set neurons another set of neurons. Let Lactive S [b] be the set of b neurons that active (linear or ReLU with nonnegative preactivation). We write [W W Jactive
TR. Taoeel Iommel
for the submatrix of W W with rows and columns from Luctive Similarly, if W' E b X C is another weight matrix from the same set of neurons to another set of e neurons then [W' lactive defined as the submatrix with rows and columns from Jactive-
When applying Lemma to specific architectures, we obtain the following:
Theorem (Matrix-wiss invariances). Recall that convolutional layer with number of input ker-
nels a, kernel size b and number of output kernels e and a tensor in gaxbxe, Under Assumptions and have the following matrix-wise invariance for a.e. time t 0:
di ([W50)T W2(1)
-[W
= O, for:
(6)
active
active
1. (Fully-comeectdd layers) W1 bgxxa and W2 E Rexb
consecutive fully-connected layers,
2. (Convolutional layers) W, convolutional, viewed as a flattening to a matrix Rex (axb), and Wa adjacent convolutional, viewed as a flattening to matrix R. (dxxexx

---

Published as a conference paper at ICLR 2022
3. (Within residual block of ResNer) W1 Y and W22 U where r(æ; U,Y, is residual block of ResNetldentiry, ResNetDiagonal or ResNetFree,
Y/ Z2
4. (Between residual blocks of ResNet) W, = UU 21J. W2 =
where r(a; Un Yj, Zz).
j E {1,2} are consecutive ResNetFree blocks,
5. comnolutiona--ulllyycommmmm (ex(axh) and W2 adjacent fully-connected layer, viewed as an rearrangement R
layers) W1 convolutional, viewed as a flattening to a matrix
6. Srnvolutional-Reeeelli Rex(axb) and W2 is rearrangement of [U Z] into an element of Rxdee where r(x; U,Y, an adjacent ResNetFree block,
block) W1 convolutional, viewed as flattening
matrix
7. (ResNetFree block-fully-commecee layers and vice versa) W1 [U Reex adjacent fullycocncccy or W1 Rxx fully-connected and W2 E Roxb adjacent
0 xgba and W₂
Y Z
ResNet block where rx;; Y, Z) the ResNetFree block.
We emphasize that the above theorem only makes local requirements on the neural network, to residual block. The only global
have local parts that either fully-connected, convolutional architecture requirement is beedforward-ness. The first point of Theorem admits an extremely simple proof for the linear fully-connected network case in Arora al. (2018) (Theorem 1).
Significance of Theorem 1 If we have set of neurons that is active throughout training (which W (t) (t)
vacuously true for linear Tayers), we can invoke an FTC and get (t) T (t) W2(0) (0) W1 (0) Wi (0) for the submatrix restricted to these neurons. Assume for simplicity that the right hand side is O, then the singular values of W, and W2 are the same for each of the cases listed in Theorem T If we can form chain of matrices whose singular values are the same by iteratively invoking Theorem[[] then all matrices considered have the same singular values as the final fully-connected layer that connects the output. Recall that our networks scalar-valuee so the final layer is a row vector, which rank and thus all layers considered in the chain have rank 1, which is useful in the next section.
Proof sketch of Theorem [ 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 W1 E Rxxa and W2 E Rexb be two consecutive fully-connected layers for some a, b. N number of vertices in these layers. Applying Equation 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 each pair among the b shared neurons between these two layers to get the off-ddagonal entries of Equation
NexI, we define layers for architectures where weights are not necessarily organized into matrices, e.g., ResNet or DenseNet.
Definition 7 (Layer). Let F C E be such that for all e + f E F, there is no path that contains both and f; and 2) the graph (V, EVF, w) is disconnected. Then F is called layer of G.
For this definition, we have the following invariance:
Lemma (Edge-wist wise invariance). Under Assumptions 7 Badd for all layers F and Ft that contain
all learnable weights, it holds that for a.e. time 2 0,
Σ (((()) cEF
Σ w²(()= = Σ 20 Σ wf(0).
FEP
cEF
FEP
Significance of Lemma matrices in ResNeeDiagonal and ResNetFree block forms 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 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 in- vertex which is input vertex with fixed input value 1.
3 A flattening of a convolutional parameter tensor and a stacking of
7

---

Published as a conference paper at ICLR 2022
4.3 PROOF SKETCH OF LEMMA 2 AND LEMMA
The proofs of Lemma 2 Lemma 3 and Theorem D share the technique of double counting paths, assume here that we working with network that is
which we explain next. For simplicity, 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 we, E E, via the smooth chain rule
0R(w)
Ov(w)
l' ((nu(a;w)) w)) y/ Owe
(8)
Sw.
T
((nu(() ye n
Σ
[1;; (si),
II wf
pEP.pae
/Ep.
where in the second line, we invoke the decomposition Lemma and emphasize that has no learnable parameters in the stable sign regime. Now multiply we the above expression get
OR(w)
We
Σ
(w))
(10)
Owe
PEP.p3e
where (w,((w) 1' (1 m)) y/ [n' w)) (Zre)p re Notice that (wp(w) 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 particular satisfying the assumption of Lemma 2 to get
Wee OR(W)
OR(w)
Σ IEIN
Σ
A,p(w) = Σ
Web Owob
(11)
Dwa
PEP.pg0
1=1
BEOUT.
Note that the only difference between Equations T0 and II is the set of paths that we are sum- ming over, and we double count this set of paths. We use the definition of gradient flow to obtain @R(w) /Ow, (t) 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 which is detailed in Appendix
Finally, to get Lemma we double count the set of all paths
4.4 NONINVARIANCE OF GENERAL RELU LAYERS
The restriction of Theorem T 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, W, for ReLU layers and show that it is not equal its counterpart W2W.T thus giving a negative result:
Lemma (Noninvariance in ReLU layers). Even under Assumptions 3 annd for time t 2 0,
df (2(() (t(t)= - (t) * 0,
(12)
for the different pairs of W1, W2 detailed in Theorem
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
5 CONSEQUENCES: LOW RANK PHENOMENON FOR NONLINEAR NONHOMOGENEOUS DEEP FEEDFORWARD NET
We apply the results from previous parts prove low-rank bias result for large class of feedfor- ward networks. To the best of our knowledge, this is the first time such 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 I we define a matrix representation of a layer:
Definition 8 (Matrix representation of a layer). The matrix representation for a ResNetFree block (,IUU,Y, Z) is UU Z): for b,e E Raxbxe convolutional tensor it is the flattening to an element of R (bxxe))); and for a fully-connected layer it is the weight matrix itself.
8

---

Published as a conference paper at ICLR 2022
Theorem 2 (Reduced alignment for non-homogeneous networks). Under Assumptions 7 and 3 let consist of an arbitrary feedforward neural network 1). followed by K 2 0 linear convolutional layers by M 2 0 layers that are either linear ResNetFree blocks or linear fully- connected layers; and finally ending with linear fully-connected layer Fin. For j E [K + M), denote by Wbit the matrix representation of the j-th layer after 1, N₂-() the number of ResNetFree blocks between j
(Tm..he (ee))))))))((K)))) [ee[k]-folowwe
and Fin exclusively and Velj) == max dim W[M+1| IllicksM min(as. by) if j I M and 1 otherwise. Then there exists constant D 2 0 fixed at initialization such that for a.e. time > 0,
I [Wb |Wb| (1)13 < D, [
(13)
8N.C)V.(()
Furthermore, assume that
Do for some j E [K M). then we have, as t + oc:
1/ min (rank( 8 vV..)) S || (t)113 || (t)) S 1,
(14)
In particular, for the last few fully- layers j with N,(1) 0 and Voli) = 1, we have:
[[WbO(O) -usill -u))))) (1)
(t)(()
1-000 O. vk E [M]
(1141, uz)
1, (15)
where uj and 0j the left and right principal singular vectors of wbl.
Corollary 1. For fully-connected networks with ReLU activations where the last K layers are lin- ear layers, trained with linearly separable data under logistic loss e, under the assumptions that R(w(()) < E(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 [4] quantify a low-rank phe- nomenon by providing 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,) and certain dimensions of convolutional layers (Vz). When the dimensions of ResNetFree layers are large, max dim W[M+1] is small and the number of imput channels of convolutional layers are large, this lower bound is strictly better than the trivial lower bound of 1/ rrank(W/e)) This is a quantification of the reduced alignment observed in (Ji & Telgarsky] 2019). In particular, for the last few fully connected layers (Fquation [5] Corollary []. the lower bound matches the upper bound of in the limit of Frobenius norm tending to infinity and the limiting weight matrices have rank 1 and adjacent layers align.
6 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 variety of nonlinear architectural structures, homogeneous and non-homogeneous, which in this context have not been addressed theoretically before. To this end, we decomposed feedforward ReLU/linear activated network into a composition of multilinear function with a tree network. If the weights converge in direction to a vector with non-zero entries, the tree is eventually fixed, allowing for chain rules differentiate through. This leads to various matrix-wise invariances between fully-connected, convolution layers and ResNet blocks, enabling us 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 wider set of architectures will strengthen The- orem 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 architectures (Ji & Telgarsky| 2020). 2020).
ACKNOWLEDGMENTS
This work was partially funded by NSF CAREER award 1553284 and NSF award 2134108. The authors thank the anonymous reviewers for their insightful feedback. We would also like to thank Matus Telgarsky for fruitful discussions on their related papers and on the Clarke subdifferential, and Kaifeng Lyu for pointing out error in earlier version of this paper.

---

Published as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit Jennifer Dy and Andreas Krause (eds.). ICML., volume 80 of Proceedings of Machine Learning Research, pp. 244-253. PMLR, 2018. URL http: http:://bbl...o
acceleration by overparameterization.
trier. de / db cttc///nnnccciiiececccccccccccct hat.mm//mmmm0000 html +AroraCH18
Jérôme Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in ma- chine learning. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 11809-108199 Curran Asso- ciates, Inc., 2020. wtRphhttt:////ooeeeeeee Paper. pdf
Anna Choromanska, MIkael Henaff, Michael Mathieu, Gerard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. In Guy Lebanon and S. V. N. Vishwanathan (eds.). Pro-
ceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Reseurch, pp. 192-204, San Diego, Califor- nia, USA, 02-12 May 2015. PMLR. htRhttts: httpttts/pppoccddnnggg mlr press/v38
choromanskal5 mlml
F.H. Clarke. Optimization and Nonsmooth Analysis. Wiley New York, 1983.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematicc, 20(1):119- 154, 2020. doi:
1100000000000009990099 URL
51
Simon S. Du, Wei Hu, and Jason D. Lee. Algorithmic regularization in learning deep homoge- neous models: Layers are automatically balanced, 2018.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality, In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning. ICML 2021. 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 3004-3014. PMLR, 2021. URL SuRLAttpp//pooeeeimg
mlr. wwwpsssssssspeeee / html
Kunihiko Fukushima. Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological Cybermeticcs, 36(4):193-202, 1980.
doi: 10.10077BF00344251. URL https:: org/ 10. htt.:a........11..11000000000330 1007/B700344251
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient de- scent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018 URL http:: https:t//ppcccee...ntteo/ nwwrinuurpp...m cc/
N.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation pat- terns. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alche Buc, E. Fox, and R. Gar- nett (eds.), Advances Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. UR//attss: http://cccsoocssccaaap/////000/0 97 9766527f2b5
pdf
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770-778 2016. doi: 10.11099VPR.2201...00
Christopher Heil. Absolute continuity and the fundamental theorem of calculus, 2019. URL
https://doo wwwggolg......o C. 1007 998-9988833 3- 030 26903-696666 6_6
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pat- tern Recognition, 2017.
10

---

Published as a conference paper at ICLR 2022
Minyoung Huh, Hossein Mobahi, Richard Zhang, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. arXiv, 2021.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In In- ternational Conference on Learning Representations, 2019. URL /
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp- 17176-17186. Curran Associates. Inc., 2020. URL /ttttp:://prccceiinngg www.ips.upppppp c (85422a554885677100 4rt.bD/aSSSBB0011115cccc44222223 http://ppppp.pppappp////////////
.ddf
Kenji Kawaguchi. Deep learning without poor local minima. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 29, Curran Associates, Inc., 2016. URL https: /ttp::://////reeeeeeeeeee nee paper/201 022006/ff11 6/ wttee/fff999990 65c 71 2c4 9d5 1 a 1aaaaaa111112233aca-aaaa
neurips.cc
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation, 2019.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning, Nature, 521(7533444446444444 2015. doi: 111038//natur115399 URL httpps///ooo..crr//...0/////////
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogencous neural net- works. In International Conference Learning Representations, 2020. httt::::
//openreview wwt.://oomm..deeeee......
Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized op- timization in deep neural networks. In Cortes, N. Lawrence, Lee, M. Sugiyama, and
R. Garnett (eds.), Advances in Neurul Information Processing Systems, volume 28, Curran Asso-
ciates, Inc., 2015. URL https: /tp eea32c96f eea22225ES20033f4422222666768682
pdf
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning, 2017.
Adityanarayanan Radhakrishnan, Eshaan Nichani, Daniel Bernstein, and Caroline Uhler. On align- ment in deep linear neural networks, 2020.
Miaoyan Wang, Khanh Dao Duc, Jonathan Fischer, and Yun S. Song. Operator norm inequalities between tensor unfoldings on the partition lattice, May 2017. ISSN 0024-3795. URL http: wtdxx.doi.ogg//11 10t.11001.11.......... laa.2017 01.0011111111
Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and landscape properties. In International Conference on Learning Representations, 2018. URL
attps://openrewwe net wor.mrid -o
A ILLUSTRATION OF LEMMA
We give a quick illustration of the two steps described in Section 3 for a fully-connected ReLU- activated network with 1 hidden layer. [ the unrolling of the neural network (Figure Tap into a tree network (Figure lb). Figure2aa 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 Figureeb 2b are coordinates of the path enumeration function (x;; i) in this example. Furthermore, weights in the tree net depend entirely the signs of the original weights. The rest of the proof argues this intuition for general ferd-forward neural nets. As a remark, in general. is a very large number- exponential in the number of layers for fully-connected net with fixed width.

---

Published as a conference paper at ICLR 2022
PI
[2]
(2)
Wt11
212
[2]
11
222
1/2
22.00
12
i11
i12
i21
1.2
201
122
222
21
322
(a)
(b)
Figure 1: Transformation of feedforward network into tree net. All nodes apart from the input nodes use ReLU activation. The two neural nets drawn here compute the same function. This idea has been used Khim Loh (2019) prove generalization bounds for adversarial risk.
0
12)
sgn (ur
sgn (w))
2/2
fsmm Lis
U1
222
sgn (wit)
(i1l 15a uss
sgnt [1)
m
wij 11 1
1.lii1 mm
121
1u12
Eeni 11
111
i11
i12
i21
122
i1
i12
i21
i22
la
[e]
iai Lx
21
922
20
Iz
(a)
(b)
Figure 2: Pulling back of weights in tree net. All nodes apart from the input nodes use the ReLU activation. The original net was drawn in Figure Ta and Tb This is possible due to the posieeit-homogeeeity of the activation function. From Figure 2b in Theorem I with weights from +1] and input from the path enumeration function h of the neural by subdividing the edge incident to the input neurons and assign weights corresponding to sgn(h(x)))
recover the final tree
B PROOF OF LEMMA II
We first prove an absolute-valuee version of Lemma 1 and show that the extension to Lemma straightforward. In other words, we first prove
is
Lemma 5 (Absolute valued decomposition). For an arbitrary feed-forward neural network v Rd RR there exists tree network p² Rea RR such that p¹ Hi where It is the
12

---

Published as a conference paper at ICLR 2022
absolute-valued path enumeration function defined as h t1(x)) = (Typ |we]
Furthermore,
pEp
the weights of pl is in {-1,1} and only depends on the sign of the weights of the original network
v.
We first give some extra notation for this section. In general, we define:
(S) to be the finite power set of some finite S.
pl N2o to be the cardinality of set When is path then it is viewed as the number edges.
To make it clear which graph are referring to, define for arbitrary feedforward neural network v: Rd + R with computation graph (G[V). G[E), G(w)):
la = ......., & to be the set of input node of G and Oa {oa} to be the set of the single output node of G.
Pg be the enumeration of all paths from any imput node in Ig to the output node og-
Hg to be the enumeration of all paths from any node v E G[V] to the output node og-
Note that if G has more than vertices then He C Pa.
Each G[V] to be equipped with fix activation d, that is saativelly--hommgeeeeeee
To be precise, G is enforced to be a DAG, connected and is simple (no self-loop, at most 1 edge between any pair of vertices), Each node of G[V] is equipped with: activation a pre-activation function defined as:
function Gv) that
v = of for some j E [d]]
(G))
(16)
[EWEIN, POST,(())s..
otherwise;
and a post-activation function defined as ([](osT(()))aa = ((((((ppe((())(()))
(17)
Note that POST,c = v.
G ep to be the vertex and edge, respectively, furthest from og some path of G.
G pp to be the unique y, such that ig P.
Definition 9 (Hasse diagram inclusion). Let be a finite set and a set C. (o() of elements in S. A Hasse diagram S is directed unweighted graph HASSE(S) (S, E) where for any p, q E S. pg E E iff p S and ggl - |p|
Definition 10 (Unrolling of feedforward neural networks). The unrolled tree neural network TO of G is free neural network with computation graph To where
Unweighted graph [Tc[V], Ta [B] HASSE(He). In particular To[V] Hg and identify vertices of To with paths in G.
Weight function Ta [w] E e pg + Glu)(ep)
Activation [a|o](v) == G[o](u,).
Lemma 6 (Unrolled network computes the same function), Fix arbitrary feedforward neural network v : dd + R with computation graph G. Let TG be the unrolled tree network of G with computation graph TG. Then TG-
Proof. We proceed with induction og == maxpeP |pl the longest path between any input node and the output node of G. In the base case, set oG 0. Then VG = {oG) singleton and the neural network computes the activation of the input and return it. Hc Vr {po} then is a singleton containing just the trivial path that has just the output vertex of and no edges. The activation function attached to Po in T. by construction, is the activation of og. Thus, 7 also simply returns the activation of the input.
Assume that TO for any with graph G such that ag S 1 for some 2 1; and for the constructed as described. We will show that the proposition is also true when v has graph with og t. Fix such and G that og We prove this induction step by:
13

---

Published as a conference paper at ICLR 2022
1. First constructing G' from G such that v where v/ is the neural network computed by G".
2. Then showing that Ta G' by constructing an isomorphism preserves E, wo and o.
GV[V] - To[V] that
The construction of G' An illustration of the following steps can be found in Figure Recall that INoG
(UI,..., Um is the set of verviccces of og.
1. Create distinct, identical copies of G: GI,..., Gm-
2. For each [m]], remove from Gj all vertices (and their adjacent edges) such that there are no directed path from a to v.y.
3. We now note that ac, t (to be argued) and invoke inductive hypothesis over G3 to get an unrolled tree network with graph T3 such that = Vj where V/ is the neural network computed by Gj-
4. Finally, construct G' by creating a new output vertex og and connect it the output vertices or, for all j E [m]. As sanity check, since each T3 is tree network, is G². More precisely,
Ti[V; (b) G'[E] {oo, or i E [m]) T
(a) G*[V] foor
(c) (') ((w](1joc) if = o0
og' for some [m] and Ty[w[[e), where
E [B) otherwise
(d) G'[o[(o) = G[o)(oc) if og and Tt)o where T,[V], otherwise.
0
W/
w1
[2]
11
1/2
1/2
11
12
Wi
12
i
1/
i2
i
12
122
(a) G
(b) G1 To,
(c) G2 To,
Figure 3: Construction of G". G₁ and G2 are the modified copies of G in step 2. In step 3, the transformation TG, happens to coincide with G; for i 1, in this case. G is created step by adding an extra vertex og and connecting it to U1 and 02 with the appropriate weights and activation and can be seen in Figure Tb
G' is well-defined We verify each steps in the above construction:
1. This step well-defined.
2. For any G5, as long as ag 2 (by definition), we always remove og from each G, in each step; since by is in-vertex of og and G is DAG. Otherwise, this step is well-defined.
14

---

Published as a conference paper at ICLR 2022
3. Fix j [m]. By construction (and since always remove og from Gj in the previous step), Og, = {v,). J. If there is a path p with length at least t in Gj. then since Gy S G[E] and OC E G[V] \ G,[V), the path p" U {oo) created by appending og to p" is valid path with length I. + 1. This violates the assumption that og = I and we conclude,
by contradiction, that og, S t 1. This justifies the invocation of inductive hypothesis for
Vj to get tree neural net Tj. 4. The final step is well-defined.
v' computes the same function for any input x E Rd
Recall that // is the neural network with graph G' We have
v/ v'(x) = (G' ())
(18)
m
G'(a](oor)
G' G'lw)(u,oo)) (G))posT((;;))())
(19)
G[o](oa)
Glu1(100c) (T) [POST] (1,)((
(20)
= G[o](ooG)
Σ (ly)())oo) (G|PoST) (19pss((1s)))c ((r)
= =v(x)
(21)
where we invoked the inductive hypothesis in the last line to get
(T) (+)s)()))) (x)) (x()) = (C[PoST](c,
(22)
and the rest are definitions.
G" is isomorphic to To Although this should be straightforward from the construction, we give formal proof. Consider the isomorphism π GV] + [v] given as
(v) OTO {oc} Ho p (oc)
if = og if
(23)
Ho, for some j E [m]]
where paths viewed set of vertices. The second case is well-defined since pU (oc) E Ha for any p E Ha, for any j E [m] by construction of Gj.
We can verify that is isomorphism between the two structures. Fix pq E G'(E]. Consider two separate cases: pq E [F] for some j and pg & Tj [E] for any j. In the first case, by definition
of T7 as a Hasse diagram, p {u,} U q are paths in Ha,- Thus, T (f)) (4) (p U {oa (q U {oa)) satisfying =(p) = [1y} } U Um)). Thus, by definition of Hasse diagram, (p) E FF]
Furthermore, G'[w] = G[w] (e,) [cl In the second case, we have pq U,0g
for some j E [m]. Thus, T(p)T(q) = (Hu, (a), E TolE] also by definition of Hasse diagram. At the same time, ('(w](pg) = G[w](1,0G) = Tal (T()(((())<(()) by definition.
Fix E G'[V]. If = og' then (v) = Glo((oG). At the same time, Talo[(T(o) = Glo)("(oc) G[o)(og) = Gv(a](v). If # og' then there is a j [m] and a ap E Ha, such that 1 = p [V]. Then by definition,
G'[a[(v) = [v) G[a](,,) Glol(ep Ufo }) = TTlo)(T(v))-
(24)
This completes the inductive proof that shows TG = v' v/ for with ag = t. By mathematical induction, the claim holds for all neural network v.
Lemma (Pull-back of numerical weights). Fix an arbitrary a feedforward neural network v : Rd R with computation graph G. Let E G[V] \ (Ig U be inner vertex of G with k in-edges e1..... C E G and a single out- f E G[E). Then the network v/ with computation graph G' = (G[V), G" [w]) defined as
Glu(() (gn(G]w]())
ife for some j E [k]
Gl[w] e G[w](e)
if
(25)
otherwise.
15

---

Published as a conference paper at ICLR 2022
computes the same function In other words, pull the numerical values of G[w](f) through u, into its in-edges; leaving behind only its sign.
When fixing input to G. sgn(GWw](F) and update 2 to 23 [][[w]]())
extend this operation to fo j [d]. By setting G2 [w](f)
Proof. Let the single verteer of v be b. If suffices to show that G[ G'[PRE (b). Fix
an input x to v. Let the k in-edges of be d1,...,. Since we only change edges incident to e, G[POST]a, G² G'[POSTJay for all j [k). We have:
G' (PEEEE (oo[Coeeeo))))GGoooe)))))CCCC (G)
(26)
= sgn(G[v[(<bb) (Glo[())
((u(() G[PoST](a,)
(27)
k
= sgn(C[uo(oo)))(G[[((bb)) ((G][(() (Glol(v))
Σ Glw](a)o) (ap[(oo])-GPPosT(((]) G[PoST](a,)
(28)
(ub) (Glo((o)
Glul(age) G(pos)(((())))))
(b)
(29)
where equation 28 is due to positive homogeneity of o. and the just definitions.
We can now give the proof of Lemma
Proof of Lemma 5 Given an arbitrary feedforward neural network v with computation graph G
(G[V), G Ej G(wl),
Lemma 6 and get the unrolled tree network To
Telw)) such that v= TG.
Let 1T; 22:.... Te be ordering of TclV) OTo ( |7| 1) by breadth first search on Te starting from OTg. In other words, if dropolu (u, OT²) > diopo OTa) then u appears after v in т,, where dropo 6) is the number of edges on the unique path from
for some b E Tc[V]. Iteratively apply Lemma 7 to vertex TI...., in To while maintaining the same function. After & such applications, we arrive at a network He with graph MG such that 14c TO v. Recall that the pull-back operation of Lemma 7 only changes the tree weights. Furthermore, the ordering chosen so that subsequent weight pull-back does not affect edges closer to OTg. Therefore, at iteration j.
1. Ma (T( (gn(G(w(((z.)) for all h s j. for some q E Mc[V] such that (mx)q Ma [
2. if ny & IMae then Mc(w[(r(T,)) = G[w](e,) II sen, [[w]]()), for some E Mc[V] such that r(T,) E Ma[E]; otherwise, n, is an input vertex corresponding to input Wryy then Try is modified to In, II,e,, [G[w]()| = hg(#n,) where hig is the absolute-valued path enumeration function.
This completes the proof.
Now we present the extension to Lemmal
Invoke Lemma to get tree network μí' such that n¹ h'. Then one can subdivide each input edges (edges that are incident to some input neuron i,) into two edges connected by 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.
Proof of Lemuaa 7
More formally, for all E P, recall that ip is a particular input neuron of μí in the decomposition lemma (Lemma D.. Since yl is tree neural network, there exists distinct node uy in p that is
16

---

Published as a conference paper at ICLR 2022
adjacent to ig. Remove the edge ipup, add neuron uig. connect ipug and upppp where the weight of the former neuron is set to sgn ITep We) and the latter to w|I wipp)((ppp)) It is straightforward to see that with constructed from above, y uu h where h is the path enumeration function.
With slight modifications to the proof technique, one can show all the results for Theorem I The- orem 2 and Corollary [ to the same matrix representation presented in the paper but with the absolute signs around them.
C PROOF OF TRAINING INVARIANCES
Claim (Directional convergence to non-vanishing point implies stable sign). Assumption 2 implies Assumption 7
Proof. Let e be the direction that wit))
[[ converges to. Let O be the orthant that v lies in. Since e
does not have a 0 entry, the ball B with radius min; |usl/2 and center is subset of the interior of
=n(t) O. Since [w(t]la converges v, there exists time T such that for all s > T, (>)
mn(s)
B. Thus,
eventually, ws)) E B where its signs stay constant.
Claim (Directional convergence does not imply stable activation). There exists a function w R Rd such that wi) converges in direction to some vector ve hut for all u E (R)), (=) has infinitely many elements. This means that for some ReLU network empirical risk function (w) whose set of nondifferentiable points D has nonempty intersection with wR)., the trajectory {wr(f) 120 can cross a boundary from one activation pattern to another an infinite number of times.
Proof. Fix a vector U E Rd.. Consider the function ++ sin(())))
Lemma 8 (Clarke partial subderivatives of inputs with the same activation pattern is the same). Assume stable sign regime (Assumption D. Let Pr, P1.P2 E P be paths of the same length L. Let E VL. Assume that for each i [L], we have us
P1 (U1...., (2) E VL and p2 {ui..... uu} and u, having the same activation pattern for each input training example, where the activation of neuron is 0 if is ReLU activated and has negative preactivation; and is 1 it is linearly activated or has nonnegative preactivation. Then 0p, p(h) = ((h) where @ is the Clarke subdifferential.
Proof. In this proof, we use the absolute-valius version of the decomposition lemma. Fix a training example j and some weight wo and let the output of the path enumeration function be h == (hp h(zy; w pep. Denote X' C R the input space of all possible pairs of values of (P1, P2) such that Assumption
D and the extra assumption that both paths have the same activation pattern on each neuron hold. Let m TR22 - R be the same function as the tree network y but with all but the two inputs at p1. P2 frozen. We will show that m is symmetric in its input. Once this establish, is trivial to invoke the definition of the Clarke subdifferential to obtain the conclusion of the lemma.
Let (a, b) E X R² We thus show that if (b, a) E X then m(a, b) = m(b, a). Recall that j is itself 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 Pp Ieeep We since the input to p is PP| and going along the path collects all signs of we for all e p.
We now invoke the 0-1 form of ReLU neural network to get m(a.b) = ((h) Epep
b) where Z, is iff all neurons on path p is active in the μ network (recall that we identify paths in a 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 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 l by construction
17

---

Published as a conference paper at ICLR 2022
and hence (p(a, b) Zp(b, for all P since activation pattern of each node of the μ network stays the same. Thus we conclude that m(a, b) = m(6, 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 are & Telgarsky (2020) which, by definition, is absolutely continuous. It then follows from real analysis that its component w. (1) is also absolutely continuous for any e E E. For absolutely continuous functions (1) for some E E, invoke the Fundamental Theorem of Calculus (FTC) (Chapter 6, (Heil 2019)), to get:
Σ (t) MEINg
E w (0)= -2 Σ MEINg
f Wuo(s) dt WEIN. [0.0]
dwar
(s)ds
(30)
We now proceed to compute duc (s). Since w(I) is absolutely continuous and we are taking the de
integral via FTC, only need to compute du (s) for a.e. time By chain rule (see for example, the first line of the proof of Lemma C.8 in Lyu & Li (2020), there exists functions (gy)ā=1 such that
gj Ov,, (w) [8(4| for all j [n] where Vag (w) (zzi w), and for a.e. time 2 0,
dw di (8)
Σ
(un w())) Vj 9j
(31)
Fix j E [n], by the inclusion chain rule, since Vx, = l o hz with and μ also locally Lipschitz, have by Theorem I.1 Ly & Li (2020),
[alpp a @u(M(w)), 33 e @Mms)b(u) }
Ouz, = O(u (w) C CONV
Σ pEp
(32)
Thus there exists (ra)a= 2 0, Ea=1 Ya that:
and (a" e (p(h(w)), 57 E ( such
9j
To
J.p"
pEP
Here we use Assumption trajectory to compute:
deduce that eventually, all weights non-zero in gradient flow
The dllta,louu)) d(w) (w) - (LE0) (Ij)p II wy
/ED.f4e
cEE
Plug this back into 9j to get:
A
Ya Σ
[alp
(xz)r
II Wf
9j =
pEp eEp
SEP.ffe
cEE
Plug this back into
du (s) and to get, coordinate-wise, for a.c. s 2 0, de
dw (s) ((ou(zaw(s))
1 Σ
Va
[a p
(xz)p
II wy(s).
(33)
dt
PEpleEp
fEn.fee
Multiply both sides with gives:
dw. (s(s)
(s)
Σ
Σ
(w)()))))
(34)
dt
pEPleEp
J=1
18

---

Published as a conference paper at ICLR 2022
where
dzy(()) = f' (((uu())))) ye Σ %a
(0))
II [w)(s)]
(35)
SEP
Note that d does not depend on the specific edge used in Equation 33 and also that the term given by does not depend and can simply write Op for Σ Ta [ Plugging back into the FTC to get:
Σ
(t)
Σ
w (0) =2
Σ
Σ PEPluvEp
1
Σ
dy)(w(())ds
(36)
MEIN, (0.1]
n2
MEIN.
MEIN
j=1
=
Σ n
(up(w(s))ds.
(37)
0.1)
PEPIDEP
j=1
Finally, by identical argument but applied to the set of edges vb for some E OUT,, we have:
Σ
(t)(t)
E
(0)(
=
/
Σ
Σ
dip(w(s))
d
(38)
1..1
n
BEOUT
BEOUT,
PEPlUEP
j=1
Σ
w (t)
Σ
w (0),
(39)
WEIN
uEIN.
which completes the proof of the first part of the lemma.
For the second part, recall that have 2 vertices u, such that IN, IN, IN and OUT, OUT, = OUT with stable activation pattern for each training example. To make it more readable, we in our notation and introduce some new ones: for some Pi-+a be the set of all paths from some input node in I to node and for some E OUT, let Po-so be the set of all paths from to the output node o. Then one can decompose the sum as
drop the explicit dependence
let
dl Wau
Σ
((p((1;;)) y. Σ ΣEΣ
Σ
(xz)m
II SEp:
Wy OppUUuaUpp
PIEPI-a bEOUT PrEPamo
(40)
where Op is the partial Clarke subdifferential at input Recall that the end goal is derive
Wan WanWav
Wan dt
War + Wan
Wou-
(41)
di
dt
Using equation equation 40 the second term on the right hand side becomes
Wav dl
Wau
(()((z))))
Σ
Σ
Σ
(42)
1=1
PIEP
bEOUT
PoEPo
(1))m Wan
II Wy
W.b
(43)
UEPr
19

---

Published as a conference paper at ICLR 2022
where the product way (Irs wy)
Wab is a jagged path. Then one continues with the deriva-
tion get
d
Σ aEIN
Wou Way
E
(Wau Wav)
(44)
dt
dt
aEIN
3 REIN Pr 11 1o P2EPo-00
(45)
(x))m=
II SEp:
(war Wub Op:UUu)Upp (15; + wau Wob Up. (23;) (1);
wi
(46)
On the other hand
Σ WebWWbb
= E
(abbweb)
(47)
dt
dt
BEOUT
beaUT
Σ
L' (yv(sy; w)) w))
E 3E
(48)
GEINDEOUT Pi I PrEPo-o
(zz)ps
II SEPLUP2
wi
(war- was (ppu( (Iz. w) + Wan Web Oppu(t)pps (zy; w)
(49)
This is where the more restrictive assumption that for each training example, and have the same activation pattern as each other (but the same activation pattern between u and v of, say 3i, may differs from that on, say x2)) Under this assumption, (p.U(u)upp (r): = Op.utopup (1r55 w) as a set. This identifies with 49 and gives us:
invoke Lemma to get
Σ BEIN
Wan (tau(t)aaa (1)
Σ (os(()mroo())
O.
(50)
dt
BEOUT
This holds for any time / where and 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
Proof of Lemma 3 The proof is identical to that of Lemma 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 2 0,
Σ REF
(s)
dwe
(s) = Σ
(wp(w(s)) (x5),
II (s)s)) FCP
(51)
dt
PEP
j=1
for any layer F.
Before continuing with the proof of Theorem I we state a classification of neurons in 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, formalize some concepts:
20

---

Published as a conference paper at ICLR 2022
Figure 4: Jagged path. Here the straight arrow denote single edge in the graph while the snaked arrow denote a path with possibly more than one edge. u and are nodes in the statement of the second part of Lemma 2 E IN = IN, IN.. b E OUT = OUT, OUT..
Definition (Convolutional tensors). Free parameters in a (bias-free) convolutional layer can be organized into tensor T E Rexbxc where is the number of input channels, b is the size of each 2D filter and 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 = 3 in this layer; filters are of size 11 x 11 so b = 121 is the size of each 2D filter; and finally, there are 96 output channels, so e 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 parame- ters T E Rexbxa, Then neurons in this layer can be organized into a two dimensional array (uj,s )ee((] for some I E N such that
1. For all j.j' E [1] and for all is E [c], Ug and vy share all its imput weights. More formally, there exists bijection d INu5, + INoy such that:
Wayg,k Wotuleyre
(52)
for all INe
2. For all j E [1] and for all ls W E [c], Vy,k and 0y has the same in-vertices and out-vertices. In other words,
IN 1N IN INu, and OUT OUTUAa OUT
(53)
For example, in the first convolutional of AlexNet in 92 the input image dimension is 224 x 224 3 pixels and the stride of the 11 x 11 x 3 filters in the layer is 4, with padding.
Thus single 2D filter traverse the image (224-
times, each corresponds a different neuron in the layer. This process is then repeated times for each output channel, for total of c l neurons the convolutional layer.
Lemma 9 (Extension of Lemma 2 to weight sharing). Let V = (15,4)))) be convolu-
tional neuron organization. Recall that by definition 12 for all j (4). IN IN1za IN; and OUT v5.1 = OUT v32 =: OUT,. We have for a.e. time
0.
Σ
(o(1)w((() ((0))()))(((0))o())))))
Σ
|=(1)2/(0) (=(0)=((0), (54)
(Murr)))))r(())
where
WVx = {ww,, w2) Vj E [1] Ba, E INj, Wayyy, = Wi and Wayny.2 = w2
and similarly,
Wour (V) {(w), W2) Vi E [1], Fby OUT,, Woy.bb wh and Wor, w2).
21

---

Published as a conference paper at ICLR 2022
Before start the proof, some remarks are in order. Let 71 2xxxxa be convolutional layer and let = (0,,k be its convolutional neuron organization. Then
Wix(V) {([T)) (Ti)a I in E [a], [6]] If furthermore T2 E Rexdx² 2 is a convolutional layer immediately after T1, then
(55)
Wour (V) {([T2) (T2 (2,))),,,,)) k1 [c], k2 [d]]
(56)
If instead of T2, the subsequent layer to Ti is fully-connected layer W e (xx((1x)) (recall that there are 21 neurons in Ti layer), then
Wour (V) = ((Wi, (Talad)x22) | 4 E [4,12 E [[]
(57)
Proof of Lemma 9
As before, the proof is identical to that of Lemma
2 with the exception being the
set of paths that we are double counting over. For all j E [4] let
A = {p1 Up2 P1 is a path from / to U3 P2 is path from 2y2 to t0.0),
(58)
and
A₁ {pl Up Pi a path from / to 132 P2 is path from 1 to o}.
(59)
Let A == Usen Aj U Az Then by an identical argument that of Lemma 2 show that
Σ (()))o((1) w(O) (0) 1 Σ
Σ dip (w())ds
(60)
10.1 PEd
(www"))
Σ
(t) =(0)2'(0).
(61)
(s,z")E
Here the notation d,, is well-defined since we do not have to specify a path for the subgradient Op. This is because are working with linear convolutional layers and thus all subgradients gradients and is evaluated to 1.
Proof of Theurem 7 All points this theorem admit the same proof technique: First, form matrices as instructed. Let X = {wi, V2, Um C V be the active neurons shared between the two layers. Check the conditions of the second part of Lemma and invoke the lemma for each pair u, X. We now apply this to each points:
1. Let W1 E Raxa be a fully-connected layer from neurons in V12 to neurons in V/2 and W2 E Rexb be fully-connected layer from V.2 Vs. Then have IN, = V and OUT, W for all u E U. Furthermore, all weights around any u are learnable for all u in U. Invoke the second part of Lemma to get the conclusion.
2. let Ti E cxxxa and T2 E Rexdxe be the convolutional tensors with convolutional neuron organization of Ti (Definition 12) being {ug,a)
Form the matrix representation W1 E (Rex(ab) and W2 E Rede)xe as per the theorem statement. By Definition 12 for k, k' E [c]. for all j [4], INo,. -NN,,e and OUT,,, OUT, Invoke Lemma get the conclusion.
3. Let r(æ; U,Y, Z) be residual block of either ResNetllentitty Res.NeDiaao or ResNet- Free. In all variants, skip connection affects neither the edges in U e go and Y E cxxb Let Y be fully-connected from neurons V1 to neurons Vz and U be fully-connected from neurons V2 neurons Vg. Then for each E V2, IN, V1 and OUT, Vg. Furthermore, all weights around any vertices in V22 are learnable. Invoke the second part Lemma 2 get the conclusion.
22

---

Published as a conference paper at ICLR 2022
4. Let r:(2;; Y, Z {1,2} be consecutive ResNetFree block. Let Yi be fully con- nected from neurons V1 to neurons V2, U1 be fully-connected from V22 to neurons Vs. Y2 be fully-connected from neurons V/3 to V4 and U2 be fully-connected from V4 to neurons Vg-
Y2
Then [U1 Zi] is fully-connected from V1 U V/ to Va and
is fully-connected from Zz
V33 V Vs. Invoke the first point to get the conclusion.
5. Let the convolutional tensor be T E Rexbxa with convolutional neuron organization (esx)jeet),.(() for some E N. Let the adjacent fully-commected layer be W E (xx()))) Form the matrix representation W E Rexab and W2 E gdixe as per the theorem state- ment. Then have for any k, k' E [c] and for all j E [7], INe,, INu =: IN, and OUTp,
OUTu3, OUT,. Invoke Lemma to get the conclusion.
6. Let r(; U, Y, Z) be residual block of either ResNetldentity, ResNetDiagonal ResNet- Free. Let Y be fully-connected from neurons Ví to neurons V2, U be fully-connected from neurons V2 neurons V3. Thus, Z is fully-connected from Vi to V3. Then W2 UU Z] is fully connected from V1 to V2 U V3. We invoke the fifth point to get the conclusion.
7. first consider the case where the ResNetFree block is followed by the fully- layer. Let r(x; U, Y, Z) be the first ResNetFree block with input neurons where Y fully-connects
neurons Vi to 1/2 and fully connects 1/2 to V3- Then we have [ Z] fully-connects V1V to Vg. If the subsequent layer is fully-connected layer then invoke the first point to get the conclusion; otherwise if the subsequent layer is a ResNetFree block r rxx; U", Y' Z")
Y
with Y' fully-comnects V/ V4 and U" fully-connects V4 Vs. Then -
fully-connects
Va to V4 U V/g and we one again invoke the first point to get the conclusion.
Proof of Lemma This is the continuation of the proof of Lemma? 2 only needs show that when is active and inactive, the expression in 46 49 not equal in general. For the sake of notation, we pick the case where the preactivation of u is strictly positive, that of strictly negative, and further assume that the whole network is differentiable at the current weights w for all training examples.
To obtain noninvariance, one
In this case, it is not hard see that the Clarke subdifferential pwp is singleton and contains the gradient of the y network. Furthermore, for any path (#1...., UL), the partial derivative 8p if all neurons on p are active and otherwise. Thus, we have
Sp
d dt OEIN
Σ War Wae
(62)
a (()((z;))) y
3V Σ Σ
Σ
(aimm
II
Wy
Was
Wab"
aEIN BEOUT active pa EP) active pa E Po-a
fEpi
(63)
We can actually factorize this even further by noticing that the term way does not depend on b and Wab does not depend Rearranging the sum and factorizes give:
d dl
Σ
Wau War
(64)
(
((y
Σ
(15)p)
II wf fEPt
Σ
II
wy
(65)
active P1 PPEP
active PrEPumo / EEp2
23

---

Published as a conference paper at ICLR 2022
On the other hand
d
Σ BEOUT
Wub Web
(66)
dt
(() .
Σ
(r))m
II SEp
ws
Σ
II
wi
(67)
active PiEr
active p2 PrEP EEp
Take, for example, an asymmetric case where the in-edges v has much larger weights than that of while out-edges of has much smaller weights than that of then 65 much larger than 67 and therefore the two expressions are not equal the general case. A symmetric initialization scheme that prevents the above asymmetry may prevent this from happens, but this requires additional sumptions and is opened to future work.
Remark Using the automatic differentiation framework while setting the gradiem of ReLU to be 1 if the preactivation is nonnegative while O otherwise, the same derivation of65 63 can be achieved. Interestingly, if one only has a single example, then the final expression of (63pmiies that the matrix d (Wr & Wk) has rank at most 2, where Wy is a weight matrix in, for example, ReLU fully-connecteed neural network. Controlling the eigenvalues under low-rand updates may allow us to bound singular values of the full weight matrices Wg- The resulting bound would not be uniform over time, but improves with training and is thus different kind of low rank result. This, however, is outside of the scope of this paper.
D PROOF OF THEOREM
First we state a helper lemma
Lemma 10 (Largest singular value of different flattening of the same tensor is close). Let E Ba,b,c be an order tensor (say convolutional weight tensor). Let Tí, T2 be the standard flattening of this tensor into an element in (axb) and R (xxe)xx respectively. Then,
7712 - 72
(68)
min
Proof. Invoke Theorem 4.8 Wang al. (201 7 and using the same notation in the same paper, have for क {(c), {a, b}} and nι2 = (16, cJ, {a)}.
dimy T2)
T 2
72212
(69)
dTm(7)
that is left is to compute the left hand side in term a, b, c. By definition, dim(T) abe and
dimy 1T, T2) = dimy ((fc), fa, b)), ((b. c), fai))
(70)
= max (Dr((c), (b. <)) Dr (fcc), (4))
(71)
max (Dr(ta, () (b. c),, Dr((a 6), {a)))
(72)
[max(c, 0)] maxx(a b)] = cmax(a, b).
(73)
Plug this in equation to to get the final result.
Lemma 11 (Shuffling layer in linear ResNetFree block preserves largest singular value up to multi- ple by 8). Recall that for a ResNetFree block r(U, Y. Z) with Y E 1x U Rexb and Rxxa
YY
there two possible rearrangement of the weights A
UU Z and B
We have
4
B
1 I
$/ ||lll
D' where D' ' 0 fixed inialization.
24

---

Published as a conference paper at ICLR 2022
Proof. Recall that by point three of Theorem | have matrix invariance
000000
U (1))()-)(()'00)) U (0) - Y(O) (0).
Note that we can obtain this form since we are only considering linear ResNetFree blocks, so all neurons active at all time for all training examples. Thus, we can invoke a FTC to get this form from the differential from in theorem
By line B.2 in Ji & Telgarsky 2019).
| 111122 DD
(74)
where D = ||U (O)U Y(OY (0)1I3 is fixed at initialization.
For positive semidefinite matrix X, denote X(X) to be the function that returns the maximum eigen- value of X. We have
B 2 (M(B B))²
(75)
(r (xTTT+ZT2))
(76)
2 v (xTT)) + (212) 2
(77)
(((T))
4 > (zT 2))
(78)
4
1
(A(OTT)
1
(M(227)
D
(79)
4
4
4
(A(OT)
+ (zz
))
2
D
(80)
8
1 (A(UUT + +zz7))
D
(81)
8
(M(AAT))
D
D 2
4 =
|
2
(82)
where 77 is by an application of Weyl's inequality for Hermitian matrices which states that X(C + D) 2 A(O) +t where is is the smallest cigenvalue D, which is nonnegative since matrices here all positive semidefinite; 779 is consequence of 74 and 8T is the application of the inequality X(C + D) S A(C) + X(D) which is another of Weyl's inequality for Hermitian matrices.
Proof of Theorem 2 Fix j E [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 Fin) via the last layer. Let W; be the matrix representation of the j-th layer among the last M + 1 layer as described in Theorem Note that even if a layer has more than one matrix representation in Theorem [ 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 be a lot more careful in the next step. For each j E [K + M). we have
(t)l?) [in(t)) = Do.
(83)
where Do [|0( || [0]]] fixed initialization.
Now, we bound the difference between the operator norm of (t) and Fin(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 D.. By matrix invariance between adjacent layers of the K + M pairs of adjacent layers.
[|7(1)11 2 CIIW++ (1) Dr:
(84)
25

---

Published as a conference paper at ICLR 2022
for C== 1/8 if the k + 1 layer is ResNetFree block (Lemma 11 C 1/ 1/min((at+1 bb+1) ) if the k + layer is convolutional layer. C' max dim W[M++] if k M (Lemma 10) and C'
otherwise; for D; = [[ (0)Wi+1 Wi),,, (O)1..
Telescope the and subtract from S 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 ||WTI///rak((W> I |[W]|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
Proof. Let be the number of layers in the network. Under the conditions stated in Corollary Lyu & Li (2020) and Ji & Telgarsky (2020) showed that [|w(()]|2 diverges. Invoke Lemma 3 for all
[
A E L 1] and sum up the results, have LIIWz
D" Σラ= (t)l l| |
D" + []u(())] where D" is constant in Thus [W, diverges for all E [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 the same o-minimal structure that contains the exponential function follows from the work of & Telgarsky (2020) and that definability is closed under function composition.
26


Reviews:
[{"review_id": "mCiYpzTLatZ", "reviewer": "Reviewer_eeoo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has several strengths: (1) The decomposition of any feedforward network into a tree network and a path enumeration mapping. This lemma is interesting and may be useful in future works. (2) Based on certain assumptions, the training invariance lemma, and the low-rank phenomenon can be extended to non-linear networks, which can be viewed as a great contribution. (3) The paper is well written and easy to follow.\n\nWeakness: \n\n(1) My main concern is that Assumption 1 and Assumption 2 are restrictive and even a bit unrealistic for some architectures. Assumption 2 seems to require the weights to go to infinity. This only happens in classification tasks, and only makes sense for homogeneous networks. For a non-homogeneous network architecture, scaling up each entry of the weight can in fact drastically change the correctness of the prediction. For example, the weights of a ResNet cannot enjoy a directional convergence since scaling up will alter the sign of the output. While the authors admit this and argue '...is widely used in practice:  most practical stopping criteria based on parameter convergence imply at least directional convergence', I do wish to see some citations to support this claim.\n\n(2) Assumption 1 certainly cannot happen for any $t>0$. It definitely can hold for those $t$ in the late phase of training. Therefore, it would be better to instead state $t>T$ for some $T$, which is a more realistic assumption. Again I am very willing to change my mind if I see any empirical evidence supporting Assumption 1($\\forall t>0$).\n\n(3) Along with the last concern, another concern is that Assumption 1 gives an impression that the key difficulties are assumed away. The invariance lemma is proved for various architectures, but almost none of those architectures can be expected to satisfy Assumption 1 for any $t>0$. If Assumption 1 is modified so that $t>T$, then the results become less impressive since the results probably only hold for the late training phase.", "summary_of_the_paper": "This paper extends several technical results: (1) the decomposition lemma that applies to any feedforward networks; (2) the training invariance lemma, both for vertices and layers, that applies to various network structures; (3) the low-rank phenomenon for non-linear, non-homogeneous networks.", "summary_of_the_review": "A very interesting paper that has certain technical contributions. The assumptions may be a bit unrealistic, but the technical results can be applied in the future. I recommend acceptance and am willing to raise scores given that my concerns are adequately addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KoVbW4rI2TL", "reviewer": "Reviewer_6P7z", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\nThe theoretical result seems significant and to the interest of the community\nThe technical lemmas (Lemma 2,3,4) are well explained. Overall the paper is well written in my opinion. \n## Weaknesses\nI think this paper would benefit from a more detailed discussion of the interpretation of Theorem 2. (see my questions) \n\n## Questions:\n- Corollary 1: Aren’t the fact that the weight vectors do converge in direction to a limiting direction with non 0 entries implied by Assumption 1?\n- I would love to see more comments and discussion around Theorem 2: To what extent (13) shows a low-rank phenomenon? What are the impact of $V_c(j)$ and $N_r(j)$ on your bound (it seems that they hurt the bound)? What is the interpretation of (14) and (15)?\n- In (15) why can we look at the inner product between $v_{j+1}$ and $u_j$ (can't they have different dimensions)? What is the interpretation of this result?\n- “In fact, the following assumption, shown in the literature, is sufficient” What do you mean by shown in the literature? Empirically shown? Do you have a citation for that?\n- Assumption 2 implies Assumption 1 only for $t \\geq t_0$. What happens if the sign for $w(t)$ changes a finite number of times and is eventually constant? Could you prove a similar result as Thm 2?\n\n## Minor remarks\n- ReLU and Relu are inconsistent across the text\n- End of Page 4 ‘This assumption is realistic…’ I guess you are talking about assumption 1. Maybe, there is a missing sentence. \n- Btw Equation 4 and 5 $OUT_v$. Also $u$ is not quantified for equation 5. \n- Pae 9 “Phenonmenon”. \n- Equation 3, Aren’t $e \\in p$ missing in the index of the sum? Also, $f$ is missing in the index of the product. \n", "summary_of_the_paper": "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)\n\nThey 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.\n", "summary_of_the_review": "The theoretical result shown is very relevant to the community and is proved under relatively weak assumptions. \nI strongly recommend accepting this paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "9yZfV0623TM", "reviewer": "Reviewer_p57R", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper gives a nice overview of the techniques used and improves on them in comparison to previous work. The sketch of proofs are quite detailed. This a quite dense paper, with many definitions (for all architectures studied) but I found it clear and well written.\n\nSome of the assumption are quite strong, such as the sign remaining fixed and the alignment to parameters with no zero weight, but at least the authors take the time to discuss these assumptions.\n\nThe final result (the convergence to a rank one solution) is new for the deep non-linear case.", "summary_of_the_paper": "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).", "summary_of_the_review": "The article proves a new result on the convergence to a rank one solution, in some quite specific setting and under some strong assumption. The techniques used are improvements over previous techniques, they are well presented and could be of independent interest.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1WiWMitLghh", "reviewer": "Reviewer_udhX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "************************************************************************************\nUpdate: Thanks to the author for the response. I think now the paper is clear, and I have raised my score. \n************************************************************************************\n\nThis paper is mostly well written. In my opinion, the training invariance is very relevant in theoretically understanding the deep neural networks and the results presented in this paper are novel and interesting.\n\nHowever, I have questions about some statements in the paper. I hope the author can clarify the following:\n1. The author stated, after Theorem 1, \"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.\" I don't see why this is true: In Theorem 1, if I understand the notation correctly, equation 6. shows the invariance of $|W_1(t)|^T|W_1(t)|-|W_2(t)||W_2(t)|^T$, where $|W_1(t)|$ is the entry-wise absolute value of $W_1(t)$. However, Arora et al. (2018) show the invariance of $W_1(t)^TW_1(t)-W_2(t)W_2(t)^T$, when using linear activation. The two matrices shown to be invariant are different.\n2. In the proof of Lemma 6, the non-absolute version of the invariance $W_1(t)^TW_1(t)-W_2(t)W_2(t)^T$ is used, I understand that Lemma 6 is true for linear networks because that matrix is invariant, but then Lemma 6 would not hold for nonlinear networks since now the matrix invariance has entry-wise absolute value?\n\nOverall, I hope the author can precisely define what is the matrix invariance for nonlinear networks, and how such invariance is used to prove Theorem 2.\n\nMinor comment: In equation (14), the inequality should only hold when taking the limit?", "summary_of_the_paper": "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. ", "summary_of_the_review": "Strength: Well written; Novel and significant results\n\nWeakness: Some statements might be wrong; Some proof needs clarification\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* Low-rank bias in nonlinear architectures. 

*Strengths:*  
- Significant theoretical contribution. 
- Well written; detailed sketch of proofs. 

*Weaknesses:* 
- More intuitions desired. 
- Restrictive assumptions. 

*Discussion:* 

Authors made efforts to improve the discussion in response to 6P7z. Authors agree with eeoo about Assumption 2 being relatively restrictive but point out that main results do not need it. They discuss Assumption 1 and revised it formulation. Reviewer eeoo was satisfied with this. Following the discussion udhX raised their score (after authors acknowledged an early problems and improved them) and found the paper well written with novel and significant results. 

*Conclusion:* 

Three reviewers consider this a good paper that should be accepted. A fourth reviewer rated it marginally above the acceptance threshold but following the discussion period explicitly recommended acceptance. I find the topic interesting, timely, relevant. In view of unanimously favorable feedback from four reviewers I am recommending accept.
Decision: Accept (Poster)