Year: 2021

Abstract:
Wide neural networks with linear output layer have been shown to be near-linear, and to have near-constant neural tangent kernel (NTK), in a region containing the optimization path of gradient descent. These findings seem counter-intuitive since in general neural networks are highly complex models. Why does a linear structure emerge when the networks become wide? In this work, we provide a new perspective on this “transition to linearity” by considering a neural network as an assembly model recursively built from a set of sub-models corresponding to individual neurons. In this view, we show that the linearity of wide neural networks is, in fact, an emerging property of assembling a large number of diverse “weak” sub-models, none of which dominate the assembly.

heading: 1 INTRODUCTION
text: Success of gradient descent methods for optimizing neural networks, which generally correspond to highly non-convex loss functions, has long been a challenge to theoretical analysis. A series of recent works including Du et al. (2018; 2019); Allen-Zhu et al. (2019); Zou et al. (2018); Oymak & Soltanolkotabi (2020) showed that convergence can indeed be shown for certain types of wide networks. Remarkably, Jacot et al. (2018) demonstrated that, when the network width goes to infinity, the Neural Tangent Kernel (NTK) of the network becomes constant during training with gradient flow, a continuous time limit of gradient descent. Based on that Lee et al. (2019) showed that the training dynamics of gradient flow in the space of parameters for the infinite width network is equivalent to that of a linear model.
As discussed in (Liu et al., 2020a), the constancy of the Neural Tangent Kernel stems from the fact that wide neural networks with linear output layer “transition to linearity” as their width increases to infinity. The network becomes progressively more linear inO(1)-neighborhoods around the network initialization, as the network width grows. Specifically, consider the neural network as a function f(θ) of its parameters θ and write the Taylor expansion with the Lagrange remainder term:
f(θ) = f(θ0) +∇f(θ0)T (θ − θ0) + 1
2 (θ − θ0)TH(ξ)(θ − θ0), (1)
where H is the Hessian, the second derivative matrix of f , and ξ is a point between θ and θ0. The “transition to linearity” is the phenomenon when the quadratic term 12 (θ− θ0)
TH(ξ)(θ− θ0) tends to zero in an O(1) ball around θ0 as the network width increases to infinity.
In particular, transition to linearity provides a method for showing that the square loss function of wide neural networks satisfy the Polyak-Lojasiewicz (PL) inequality which guarantees convergence of (Stochastic) Gradient Descent to a global minimum (Liu et al., 2020b).
While the existing analyses demonstrate transition to linearity mathematically, the underlying structure of that phenomenon does not appear to be fully clear. What structural properties account for it? Are they specific to neural networks, or also apply to more general models?
In this paper, we aim to explain this phenomenon from a more structural point of view and to reveal some underlying mechanisms. We provide a new perspective in which a neural network, as well as
each of its hidden layer neurons before activation, can be viewed as an “assembly model”, built up by linearly assembling a set of sub-models, corresponding to the neurons from the previous layer. Specifically, a (l + 1)-layer pre-activation neuron
α̃(l+1) = 1√ m m∑ i=1 wiα (l) i ,
as a linear combination of the l-th layer neurons α(l)i , is considered as an assembly model, whereas the l-layer neurons α(l)i are considered as sub-models. Furthermore, each pre-activation α̃ (l) i is also an assembly model constructed from (l − 1)-th layer neurons α(l−1)i . In this sense, the neural network is considered as a multi-level assembly model. To show O(1)-neighborhood linearity, we prove that the quadratic term in the Taylor expansion Eq.(1) vanishes in O(1)-neighborhoods of network initialization, as a consequence of assembling sufficiently many sub-models .
To illustrate the idea of assembling, we start with a simple case: assembling independent sub-models in Section 2. The key finding is that, as long as the assembly model is not dominated by one or a few sub-models, the quadratic term in the Taylor expansion Eq.(1) becomes small in O(1)neighborhoods of the parameter space when the number of sub-models m is tends to infinity. This means that as m increases to infinity, the assembly model becomes a linear function of parameters. Since we put almost no requirements on the form of sub-models, it is the assembling process that results in the linearity of the assembly model. This case includes two-layer neural networks as examples.
For deep neural networks (Section 3), we consider a neural network as a multi-level assembly model each neuron is considered as an assembly model constructed iteratively from all the neurons from the previous layer. We then follow an inductive argument: using near-linearity of previous-layer pre-activation neurons to show the linearity of next-layer pre-activation neurons. Our key finding is that, when the network width is large, the neurons within the same layer become essentially independent to each other in the sense that their gradient directions are orthogonal in the parameter space. This orthogonality allows for the existence of a new coordinate system such that these neuron gradients are parallel to the new coordinate axes. Within the new coordinate system, one can apply the argument of assembling independent sub-models, and obtain the O(1)-neighborhood linearity of the pre-activation neurons, as well as the output of the neural network.
We further point out that this assembling viewpoint and the O(1)-neighborhood linearity can be extended to more general neural network architectures, e.g., DenseNet.
We end this section by commenting on a few closely related concepts and point out some of the differences.
Boosting. Boosting (Schapire, 1990; Freund, 1995), which is a popular method that combines multiple “weak” models to produce a powerful ensembe model, has a similar form with the assembly model, Eq.(4), see, e.g., Friedman et al. (2000). However, we note a few key differences between the two. First, in boosting, each “weak” model is trained separately on the dataset and the coefficients (i.e., vi in Eq.(4)) of the weak models are determined by the model performance. In training an assembly model, the “weak” sub-models (i.e., hidden layer neurons), are never directly evaluated on the training dataset, and the coefficients vi are considered as parameters of the assembly model and trained by gradient descent. Second, in boosting, different data samples may have different sample weights. In assembling, the data samples always have a uniform weight.
Bagging and Reservoir computing. Bagging (Breiman, 1996) and Reservoir computing (Jaeger, 2001) are two other ways of combining multiple sub-models to build a single model. In bagging, each sub-model is individually trained and the ensemble model is simply the average or the max of the sub-models. In reservoir computing, each sub-model is fixed, and only the coefficients of the linear combination are trainable.
Notation. We use bold lowercase letters, e.g., v, to denote vectors, capital letters, e.g., W , to denote matrices. We use ‖ · ‖ to denote the Euclidean norm of vectors and spectral norm (i.e., matrix 2-norm) for matrices. We denote the set {1, 2, · · · , n} as [n]. We use ∇wf to denote the
partial derivative of f with respect to w. When w represents all of the parameters of f , we omit the subscript, i.e.,∇f .

heading: 2 ASSEMBLING INDEPENDENT MODELS
text: In this section, we consider assembling a sufficiently large number m of independent sub-models and show that the resulting assembly model is (approximately) linear in O(1)-neighborhood of the model parameter space.
Ingredients: sub-models. Let’s consider a set of m (sub-)models {gi}mi=1, where each model gi, with a set of model parameters wi ∈ Di ⊂ Pi = Rpi , takes an input x ∈ Dx ⊂ Rd and outputs a scalar prediction gi(wi;x). Here Pi is the parameter space of sub-model gi and Dx is the domain of the input. By independence, we mean that any two distinct models gi and gj share no common model parameters: Pi ∩ Pj = {0}, ∀i 6= j ∈ [m]. (2) In this sense, the change of gi’s output, as a result of change of it parameters wi, does not affect the outputs of the other models gj where j 6= i. In addition, we require that there is no dominating sub-models over the others. Specifically, we assume the following in this section: Assumption 1 (No dominating sub-models). There exists a constant c ∈ (0, 1) independent of m such that, for any parameter setting {wi : wi ∈ Di}mi=1 and input x ∈ Dx,
median[|g1(w1;x)|, · · · , |gm(wm;x)|] max[|g1(w1;x)|, · · · , |gm(wm;x)|] ≥ c. (3)
Further more, we assume that max[|g1(w1;x)|, · · · , |gm(wm;x)|] ∈ [a, b] ⊂ R for some constants a > 0 and b > 0. Remark 1. This assumption guarantees that most of the outputs of the sub-models are at the same order, typically O(1). It makes sure that the resulting assembly model is not dominated by one or a minor portion of the sub-models. This is typically seen for the neurons of neural networks.
We further make the following technical assumption, which is common in the literature. Assumption 2 (Twice differentiablity and smoothness). Each sub-model gi is twice differentiable with respect to the parameters wi, and is β-smooth in the parameter space: there exists a positive number β such that, for any i ∈ [m],
‖∇gi(wi;x)−∇gi(w′i;x)‖ ≤ β‖wi −w′i‖.
This assumption makes sure that for each gi, the gradient is well-defined and its Hessian has a bounded spectral norm.
Assembly model. Based on these sub-models {gi}mi=1, we construct an assembly model (or supermodel) f , using linear combination as follows:
f(θ;x) := 1
s(m) m∑ i=1 vigi(wi;x), (4)
where vi is the weight of the sub-model gi, and 1/s(m), as a function of m, is the scaling factor. Here, we denote θ as the set of parameters of the assembly model, θ := (w1, . . . ,wm). The total number of parameters that f has is p = ∑m i=1 pi. Typical choices for the weights vi are setting vi = 1 for all i ∈ [m], or random i.i.d. drawing vi from some zero-mean probability distribution. Remark 2. For the ease of analysis and simplicity of notation, we assumed that the outputs of assembly model f and sub-models gi are scalars. It is not difficult to see that our analysis below also applies to the scenarios of finite dimensional model outputs.
The scaling factor 1/s(m). The presence of the scaling factor 1/s(m) is to keep the output of assembly model f at the order O(1) w.r.t. m. In general, we expect that s(m) grows with m. In particular, when vi are chosen i.i.d. from a probability distribution with mean zero, e.g., {−1, 1},
the sum in Eq.(4) is expected to be of the order √ m, under the Assumption 1. In this case, the scaling factor 1/s(m) = O(1/ √ m).
Now, we will show the the assembly model f has a small quadratic term in its Taylor expansion, when the size of the set of sub-models i.e. m, is sufficiently large. Theorem 1. Consider the assembly model f constructed in Eq.(4) with each vi either set to be 1 or randomly drawn from {−1, 1}, and suppose Assumption 1 and 2 hold. Given a positive number R > 0 and a parameter setting θ0 ∈ Rp, for any θ ∈ Rp such that ‖θ− θ0‖ ≤ R, the absolute value of the quadratic term in Taylor expansion Eq.(1) is bounded by:∣∣∣∣12(θ − θ0)TH(ξ)(θ − θ0)
∣∣∣∣ ≤ βR22s(m) . (5) Proof. In what follows, we don’t explicitly write out the dependence on θ and x in the Hessian H := ∂
2f ∂θ2 , for simplicity of notation. We further denote Hgi := ∂2gi ∂w2i as the Hessian of gi.
We decompose the assembly model Hessian H as a linear combination of Hgi . By the definition of the assembly model in Eq.(4), an arbitrary entry Hjk of the Hessian can be written as: Hjk =
1 s(m) ∑m i=1 vi ∂2gi ∂θj∂θk
. Here θj , θk are two individual parameters of the assembly model f . Note that ∂2gi ∂θj∂θk
is non-zero, only if both θj and θk are parameters of sub-model gi, i.e., θj , θk ∈ Pi. Hence, the assembly model Hessian can be decomposed as a linear combination of sub-model Hessians: H = 1s(m) ∑m i=1 viHgi . Therefore, the quadratic term becomes
1
s(m) m∑ i=1 vi [ 1 2 (θ − θ0)THgi(ξ)(θ − θ0) ] = 1 s(m) m∑ i=1 vi [ 1 2 (wi −wi,0)THgi(ξ)(wi −wi,0) ] and its absolute value is bounded by∣∣∣1 2 (θ − θ0)TH(ξ)(θ − θ0) ∣∣∣ ≤ 1 2s(m) m∑ i=1 |vi| · ‖Hgi‖ · ‖wi −wi,0‖2 ≤ β 2s(m) m∑ i=1 ‖wi −wi,0‖2
In the second inequality, we used that |vi| = 1 and that gi is β-smooth. Because of the independence of the sub-models as seen in Eq.(2), the summation in the above equation becomes ‖θ−θ0‖2, which is bounded by R2, as stated in the theorem condition. Therefore, we conclude the theorem.
It is important to note that β is a constant and 1/s(m) = O(1/ √ m). Then we have the following corollary in the limiting case. Corollary 1. Consider the assembly model f under the same setting as in Theorem 1. If the number of sub-models m increases to infinity, then for all parameter θ0 and input x, the quadratic term∣∣∣1
2 (θ − θ0)TH(ξ)(θ − θ0) ∣∣∣→ 0, (6) as long as θ is within an O(1)-neighborhood of θ0, i.e., ‖θ − θ0‖2 ≤ R for some constant R > 0.
Example: Two-layer neural networks. A good example of this kind of assembly model is the two-layer neural network. A two-layer neural network is mathematically defined as:
f(W,v;x) = 1√ m m∑ i=1 uiσ(w T i x), (7)
wherem is the number of hidden layer neurons, σ(·) is the activation function, x ∈ Rd is the network input, and W ∈ Rm×d and u ∈ Rm are the parameters for the first and second layer, respectively. Here, we can view the i-th hidden neuron and all the parameters wi and ui that connect to it as the i-th sub-model: gi = uiσ(wTi x). We see that these sub-models do not share parameters, and each sub-model has d+ 1 parameters. In addition, the weights of the sub-models are all 1. By Corollary 1, the two-layer neural network becomes a linear model in any O(1)-neighborhoods, as the network widthm increases to infinity. This is consistent with the previous observation that a two-layer neural network transitions to linearity Liu et al. (2020a).
Gaussian distributed weights vi. Another common way to set the weights vi of the sub-models is to independently draw each vi fromN (0, 1). In this case, vi is unbounded, but with high probability the quadratic term is still O(log(m)/ √ m). Please see the detailed analysis in Appendix A.
Hierarchy of assembly models. In principle, we can consider the assembly model f , together with multiple similar models independent to each other, as sub-models, and construct a higher-level assembly model. Repeating this procedures, we can have a hierarchy of assembly models. Our analysis above also applies to this case and each assembly model is also O(1)-neighborhood linear, when the number of its sub-models is sufficiently large. However, one drawback of this hierarchy is that the total number of parameters of the highest level assembly model increase exponentially with the number of levels. We will see shortly that wide neural networks, as a hierarchy of assembly models, allows overlapping between sub-models, but still keeping the O(1)-neighborhood linearity.

heading: 3 DEEP NEURAL NETWORKS AS ASSEMBLING MODELS
text: In this section, we view deep neural networks as multi-level assembly models and show how the O(1)-neighborhood linearity arises naturally as a consequence of assembling.
Setup. We start with the definition of multi-layer neural networks. A L-layer full-connected neural network is defined as follows:
α(0) = x,
α(l) = σ(α̃(l)), α̃(l) = 1
√ ml−1
W (l)α(l−1), ∀l = 1, 2, · · · , L, (8)
f = α̃(L),
where σ(·) is the activation function and is applied entry-wise above. We assume σ(·) is twice differentiable to make sure that the network f is twice differentiable and its Hessian is well-defined. We also assume that σ(·) is an injective function, which includes the commonly used sigmoid, tanh, softplus, etc. In the network, with ml being the width of l-th hidden layer, α̃(l) ∈ Rml (called preactivations) and α(l) ∈ Rml (called post-activations) represent the vectors of the l-th hidden layer neurons before and after the activation function, respectively. Denote θ := (W (1), . . . ,W (L)), with W (l) ∈ Rml−1×ml , as all the parameters of the network, and θ(l) := (W (1), . . . ,W (l)) as the the parameters before layer l. We also denote p and p(l) as the dimension of θ and θ(l), respectively. Denote θ(α(l)i ) as the set of the parameters that neuron α (l) i depends on.
This neural network is typically initialized following Gaussian random initialization: each parameter is independently drawn from normal distribution, i.e., (W (l)0 )ij ∼ N (0, 1). In this paper, we focus on the O(1)-neighborhood of the initialization θ0. As pointed out by Liu et al. (2020a), the whole gradient descent trajectory is contained in a O(1)-neighborhood of the initialization θ0 (more precisely, a Euclidean ball B(θ0, R) with finite R).
Overview of the methodology. As it is defined recursively in Eq.(8), we view the deep neural network as a multi-level assembly model. Specifically, a pre-activation neuron at a certain layer l is considered as an assembly model constructed from the post-activation neurons at layer l − 1, at the same time its post-activation also serves as a sub-model for the neurons in layer l+ 1. Hence, a preactivation α̃(l)i is an l-level assembly model, and the post-activation α (l) i is a (l+1)-level sub-model. To prove the O(1)-neighborhood linearity of the neural network, we start from the linearity at the first layer, and then follow an inductive argument from layer to layer, up to the output. The main argument lies in the inductive steps, from layer l to layer l+ 1. Our key finding is that, in the infinite width limit, the neurons within the same layer become independent to each other, which allows us using the arguments in Section 2 to prove the O(1)-neighborhood linearity. Since the exact linearity happens in the infinite width limit, in the following analysis we take m1,m2, . . . ,mL−1 → ∞ sequentially, the same setting as in Jacot et al. (2018). Note that for neural networks that finite but large network width, the linearity will be approximate; the larger the width, the closer to linear.

heading: 3.1 BASE CASE: FIRST AND SECOND HIDDEN LAYER.
text: The first hidden layer pre-activations are defined as: α̃(1) = 1√m0W (1)x, where m0 = d. It is obvious that each element of α̃(1) is linear in its parameters. Each second layer pre-activation α̃ (1) i , i ∈ [m2] can be considered as a two-layer neural network with parameters {W (1),w (2) i }, where w(2)i is the i-th row of W (2). As we have seen in Section 2, the sub-models of a two-layer neural network share no common parameters, and the assembly model, which is the network itself, is O(1)-neighborhood linear in the limit of m1 →∞.
3.2 FROM LAYER l TO LAYER l + 1.
First, we make the induction hypothesis at layer l.
Assumption 3 (Induction hypothesis). Assume that all the l-th layer pre-activation neurons α̃(l) are O(1)-neighborhood linear in the limit of m1, . . . ,ml−1 →∞.
Under this assumption, we will first show two key properties about the sub-models, i.e., the l-th layer post-activation neurons α(l): (1) level sets of these neurons are hyper-planes with co-dimension 1 in O(1)-neighborhoods; (2) normal vectors of these hyper-planes are orthogonal with probability one in the infinite width limit.
Setup. Note that l-th layer neurons only depend on the parameters θ(l). Without ambiguity, denote the parameter space spanned by θ(l) as P . We can write θ(l) as
θ(l) = θ(l−1) ∪w(l)1 ∪ . . . ∪w(l)ml ,
where w(l)i is the i-th row of the weight matrix W (l). One observation is that the set of parameters of neuron α(l)i is θ(α (l) i ) = θ
(l−1) ∪ w(l)i . Namely, θ(l−1) are shared by all l-layer neurons and each parameter in w(l)i is privately owned by only one neuron α (l) i . Hence, we can decompose the
parameter space P as: P = ⊕ml
i=0 Pi, where common space P0 is spanned by θ(l−1) and the private spaces Pi, i 6= 0, are spanned by w(l)i . Define a set of projection operators {πi} ml i=0 such that, for
any vector z ∈ P , πi(z) ∈ Pi, and ∑ml i=0 πi(z) = z.
Property 1: Level sets of neurons are hyper-planes. The first key observation is that each of the l-th layer post-activations α(l) has linear level sets in the O(1)-neighborhoods. Theorem 2 (Linear level sets of neurons). Assume the induction hypothesis Assumption 3 holds. Given a fix input x, for each post-activation α(l)i , i ∈ [ml], the level set
Sc := {θ(l) : α(l)i (θ (l);x) = c} ∩ N (θ0), (9)
is linear or an empty set, for all c ∈ R, where N (θ0) is an O(1)-neighborhood of θ0. Moreover, these level sets are parallel to each other: for any c1, c2 ∈ R, if Sc1 6= ∅ and Sc2 6= ∅, then Sc1 and Sc2 are parallel to each other. Remark 3. With abuse of notation, we did not explicitly write out the dependence of the level set on the neuron α(l)i , the input x, and the network initialization θ0.
Proof. First, note that all the pre-activation neurons α̃(l) are linear in N (θ0) in the limit of m1, . . . ,ml−1 → ∞, as assumed in the induction hypothesis. This linearity of these function guarantees that all the level sets of the pre-activations {θ(l) : α̃(l)i (θ(l);x) = c} ∩ N (θ0), for all c ∈ R and i ∈ [ml] are either linear or empty sets, and they are parallel to each other. Since the activation function σ(·) is element-wisely applied to the neurons, it does not change the shape and direction of the level sets. Specifically, if {θ(l) : α(l)i (θ(l);x) = c} is non-empty, then
{θ(l) : α(l)i (θ (l);x) = c} = {θ(l) : α̃(l)i (θ (l);x) = σ−1(c)}.
Therefore, {θ(l) : α(l)i (θ;x) = c}∩N (θ0) is linear or an empty set, and the activation function σ(·) preserves the parallelism.
This means that, although each of the neurons α(l) is constructed by a large number of neurons in previous layers containing tremendously many parameters and is transformed by non-linear functions, it actually has a very simple geometric structure. A geometric view of the post-activation neurons is illustrated in Figure 1.
As the neurons have scalar outputs and σ(·) is injective by assumption, each level set is a piece of a co-dimension 1 hyper-plane in the p-dimensional parameter space P . Hence, at each point of the hyper-plane there exists a unique (up to a negative sign) unit-length normal vector n, which is perpendicular to the hyper-plane. A direct corollary of the
linearity of the level sets, Theorem 2, is that the normal vector n is identical everywhere in theO(1)neighborhood N (θ0).
Corollary 2. Assume the induction hypothesis Assumption 3 holds. Given a specific neuron α(l)i and an input x, for any θ(l)1 , θ (l) 2 ∈ P ∩N (θ0), n(θ (l) 1 ) = n(θ (l) 2 ).
Hence, we can define ni as the normal vector for each neuron α (l) i . The next property is about the set of normal vectors {ni}mli=1. Property 2: Orthogonality of normal vectors ni. Now, let’s look at the directions of the normal vectors ni. Note that the neuron α (l) i does not depend on the parameters w (l) j for any j 6= i, hence πj(ni) = 0 for all j /∈ {i, 0}. That means: Proposition 1. For all i ∈ [ml], the normal vector ni resides in the sub-space Pi ⊕P0, and can be decomposed as ni = πi(ni) + π0(ni).
As πi(ni) ∈ Pi, and Pi ∩ Pj = {0} for i 6= j, the components {πi(ni)}mli=1 are orthogonal to each other: πi(ni) ⊥ πj(nj), for all i 6= j ∈ [ml]. (10) By Proposition 1, to show the the orthogonality of the normal vectors {ni}mli=1, it suffices to show the orthogonality of {π0(ni)}mli=1. Since it is perpendicular to the corresponding level sets, the normal vector ni is parallel to the gradient ∇α(l)i , up to a potential negative sign. Similarly, the projection π0(ni) is parallel to the partial gradient∇θ(l−1) α̃ (l) i .
By the definition of neurons in Eq.(8) and the constancy of ni in the neighborhood N (θ0), we have
(∇θ(l−1) α̃ (l) i )
T = 1
√ ml−1
(w (l) i,0) T∇α(l−1). (11)
Here, because α(l−1) is an ml-dimensional vector, ∇α(l−1) is an ml × p(l−1) matrix, where p(l−1) denotes the size of θ(l−1). It is important to note that the matrix∇α(l−1) is shared by all the neurons in layer l and is independent of the index i, while the vector w(l)i,0, which is w (l) i at initialization, is totally private to the l-th layer neurons.
Recall that the vectors {w(l)i,0} ml i=1 are independently drawn from N (0, Iml−1×ml−1). As is wellknown, when the vector dimension ml−1 is large, these independent random vectors {w(l)i,0} are nearly orthogonal. When in the infinite width limit, the orthogonality holds with probability 1:
∀ > 0, lim ml−1→∞
P ( 1
ml−1 |(w(l)i,0) Tw (l) j,0| ≥
) = 0, for any i 6= j ∈ [ml]. (12)
From Eq.(11), we see that the partial gradients {∇θ(l−1) α̃ (l) i } ml i=1 are in fact the result of applying a universal linear transform, i.e., ∇α(l−1), onto a set of nearly orthogonal vectors. The following lemma shows that the vectors remain orthogonal even after this linear transformation.
Lemma 1.
∀ > 0, lim ml−1→∞
P (∣∣∣(∇θ(l−1) α̃(l)i )T∇θ(l−1) α̃(l)j ∣∣∣ ≥ ) = 0, for any i 6= j ∈ [ml]. (13)
See the proof in Appendix B.
Recalling Eq.(10) and the fact that the normal vectors π0(ni) are parallel to the gradients ∇θ(l−1) α̃(l), we immediately have that these normal vectors are orthogonal with probability 1, in the limit of ml−1 →∞, as stated in the following theorem. Theorem 3 (Orthogonality of normal vectors).
∀ > 0, lim ml−1→∞
P (∣∣nTi nj∣∣ ≥ ) = 0, for any i 6= j ∈ [ml]. (14)
Remark 4. As seen in Section 2, a two-layer neural network Eq.(7) is an assembly model with independent sub-models. The normal vectors {ni}mli=1 are exactly orthogonal to each other, even for finite hidden layer width.
This orthogonality allows the existence of a new coordinate system such that all the normal vectors are along the axes. Specifically, in the old coordinate system O, each axis is along an individual neural network parameter θk ∈ θ with k ∈ [p]. After an appropriate rotation, O can be transformed to a new coordinate system O′ such that each normal vector ni is parallel to one of the new axes. See Figure 2 for an illustration. Denote θ′ as the set of new parameters that are long the axes of new coordinate system O′: θ′ = Rθ, where R is a rotation operator.
The interesting observation is that each neuron α(l)i essentially depends on only one new parameter θ′i ∈ θ′, because its gradient direction is parallel
with one normal vector ni and ni is along one axis in the new coordinate system O′. Moreover, different neurons depends on different new parameters, as normal vectors are never parallel. Hence, these neurons are essentially independent to each other. This view actually allows us to use the analysis for assembling independent models in Section 2 to show the O(1)-neighborhood linearity at layer l + 1, as follows.
Linearity of the pre-activations in layer l+1. Having the properties for neurons in layer l discussed above, we are now ready to analyze the the pre-activation neurons α̃(l+1) in layer l+ 1 as assembly models. Recall that each pre-activation α̃(l+1) is defined as:
α̃(l+1) = 1 √ ml ml∑ i=1 w (l+1) j α (l) j . (15)
Without ambiguity, we omitted the index i for the pre-activation α̃(l+1) and the weights w(l+1).
We want to derive the quadratic term (i.e., the Lagrange remainder term) of α̃(l+1) in its Taylor expansion and to show it is arbitrarily small, in theO(1)-neighborhoodN (θ0). First, let’s consider the special case where the parameters w(l+1) are fixed, i.e., w(l+1) = w(l+1)0 , and α̃
(l+1) only depends on θ(l). This case conveys the key concepts of the O(1)-neighborhood linearity after assembling. We will relax this constraint in Appendix C.
Consider an arbitrary parameter setting θ ∈ N (θ0), and let R := ‖θ − θ0‖ = O(1). By the definition of assembly model α̃(l+1) in Eq.(15), the quadratic term in its Taylor expansion Eq.(1) can be decomposed as:
1 2 (θ − θ0)THα̃(l+1)(ξ)(θ − θ0) = 1 √ ml ml∑ i=1 w (l+1) i,0 [ 1 2 (θ − θ0)THα(l)i (ξ)(θ − θ0) ] . (16)
where Hα̃(l+1) = ∂2α̃(l+1)
∂θ2 and Hα(l)i =
∂2α (l) i
∂θ2 are the Hessians of α̃ (l+1) and α(l)i , respectively, and
ξ ∈ P is on the line segment between θ(l) and θ(l)0 . We bounded the term in the square bracket using a treatment analogous to Theorem 1. First, as seen in Property 1, the level sets of α(l)i are hyper-planes with co-dimension 1, perpendicular to ni. Then the value of α(l)i only depends on the component (θ − θ0)Tni, and Hessian Hα(l)i is rank 1 and can be written as H
α (l) i = cnin T i , with some constant c ≤ β. Hence, we have∣∣∣(θ − θ0)THα(l)i (ξ)(θ − θ0)∣∣∣ = c ((θ − θ0)Tni)2 ≤ β ((θ − θ0)Tni)2 .
Here β is the smoothness of the sub-model, i.e., post-activation α(l). By Eq.(16), we have:
1
2 ∣∣(θ − θ0)THα̃(l+1)(ξ)(θ − θ0)∣∣ ≤ β2√ml max(|w(l+1)i,0 |) ml∑ i=1 ( (θ − θ0)Tni )2 . (17)
Second, by the orthogonality of normal vectors as in Theorem 3, we have
ml∑ i=1 ( (θ − θ0)Tni )2 ≤ ‖θ − θ0‖2 = R2. (18) Combining the above two equations, we obtain the following theorem which upper bound the magnitude of the quadratic term of α̃(l+1):
Theorem 4 (Bounding the quadratic term). Assume that the parameters in layer l + 1 are fixed to the initialization. For any parameter setting θ ∈ N (θ0),
1
2 ∣∣(θ − θ0)THα̃(l+1)(ξ)(θ − θ0)∣∣ ≤ βR2√ml max(|w(l+1)i,0 |). (19) For the Gaussian random initialization, the above upper bound is of the order O(log(ml)/ √ ml). Hence, as ml →∞, the quadratic term of pre-activation α̃(l+1) in the (l+ 1)-th layer vanishes, and the function α̃(l+1) becomes linear.
Concluding the induction analysis. Applying the analysis in Section 3.2, Theorem 2 - 4, with a standard induction argument, we conclude that the neural network, as well as each of its hidden pre-activation neurons, is O(1)-neighborhood linear, in the infinite network width limit, m1, . . . ,mL−1 →∞.
Extension to other architectures. In Appendix D, we further show that the assembly analysis and the O(1)-neighborhood linearity also hold for DenseNet (Huang et al., 2017).

heading: 4 CONCLUSION AND FUTURE DIRECTIONS
text: In this work, we viewed a wide fully-connected neural network as a hierarchy of assembly models. Each assembly model corresponds to a pre-activation neuron and is linearly assembled from a set of sub-models, the post-activation neurons from the previous layer. When the network width increases to infinity, we observed that the neurons within the same hidden layer become essentially independent. With this property, we shown that the network is linear in an O(1)-neighborhood around the network initialization.
We believe the assembly analysis and the principles we identified, especially the essential independence of sub-models, and their iterative construction, are significantly more general than the specific structures we considered in this work, and, for example, apply to a broad range of neural architectures. In future work, we aim to apply the analysis to general feed-forward neural networks, such as architectures with arbitrary connections that form an acyclic graph.

heading: A RANDOM SUB-MODEL WEIGHTS WITH GAUSSIAN DISTRIBUTION
text: Let’s consider the case where the weights vi of the sub-models are randomly drawing from Gaussian distributions, for example the normal distribution N (0, 1). That is
f(θ;x) = 1
s(m) m∑ i=1 vigi(wi;x), (20)
where vi’s are randomly drawn from N (0, 1). In this case, there is no strict upper bounded on the absolute values of weights |vi|. But with high probability, we can still bound them using the following lemma. Lemma 2. Let v1, ..., vm be i.i.d. Gaussian variables. Then with probability at least 1 − 2e−0.5 log
2m+logm, max i∈[m] |vi| ≤ logm.
The above lemma can be obtained by letting t = logm in Eq.(2.10) in Vershynin (2018) and using union bound.
Using the same analysis as in the proof of Theorem 1, we have, with probability at least 1− 2e−0.5 log2m+logm,∣∣∣1 2 (θ − θ0)TH(ξ)(θ − θ0) ∣∣∣ ≤ 1 2s(m) m∑ i=1 |vi| · ‖Hgi‖ · ‖wi −wi,0‖2 ≤ β logm 2s(m) m∑ i=1 ‖wi −wi,0‖2
Under Assumption 2, β is a constant. Note that as the number of m goes to infinity, the probability 1− 2e−0.5 log2m+logm converges to 1. Since 1/s(m) is O(1/
√ m), hence, we get∣∣∣1
2 (θ − θ0)TH(ξ)(θ − θ0) ∣∣∣ = O( logm√ m ) . (21)
When m→∞, the quadratic term of the Taylor expansion converges to 0, with probability 1.

heading: B PROOF OF LEMMA 1
text: As in Eq. (11), the partial gradient ∇θ(l−1) α̃ (l) i can be written as: (∇θ(l−1) α̃ (l) i ) T = 1√ ml−1 (w (l) i,0) T∇α(l−1). Hence, we have
(∇θ(l−1) α̃ (l) i ) T∇θ(l−1) α̃ (l) j =
1
ml−1 (w
(l) i,0) T∇α(l−1)(∇α(l−1))T (w(l)j,0).
Note that w(l)i,0 and w (l) j,0 are independent to each other when i 6= j, and ∇α(l−1) is a fixed matrix independent of w(l)i,0 and w (l) j,0. Denote aj := ∇α(l−1)(∇α(l−1))Tw (l) j,0 ∈ Rml−1 . Then,
(∇θ(l−1) α̃ (l) i ) T∇θ(l−1) α̃ (l) j =
1
ml−1 (w
(l) i,0) Taj , (22)
the inner product of two independent vectors w(l)i,0 and aj with a scaling factor 1/ml−1.
When conditioned on the vector aj , the quantity in Eq.(22) is a Gaussian variable:
1
ml−1 (w
(l) i,0) Taj ∼ N
( 0, aTj aj
m2l−1
) ,
because w(l)i is initialized following N (0, I). In the limit of ml−1 → ∞, if the variance aTj aj m2l−1 converges to 0, then this Gaussian variable should also converges to zero with probability 1, from which we can conclude the lemma. In the following, we will show that the variance aTj aj
m2l−1 converges
to 0 with probability 1 in this limit.
First, we need the following lemma to upper bound the spectral norm of∇α(l). The proof is deferred to Section B.1.
Lemma 3. Consider the neural networks defined in Eq.(8) with random Gaussian initialized parameters. There exist a constant C > 0, such that, with probability at least 1− 4(l + 1)e−m/2, we have
‖∇α(l)(∇α(l))T ‖ ≤ C,
with m = min{m1,m2, . . . ,ml−1}.
Since aj = ∇α(l−1)(∇α(l−1))Tw(l)j,0, using Lemma 3, we can bound ‖aTj aj‖ by
‖aTj aj‖ ≤ ‖∇α(l−1)(∇α(l−1))T ‖2‖w (l) j,0‖ 2 ≤ C2‖w(l)j,0‖ 2.
Recall that w(l)j,0 ∈ Rml−1 follows the Gaussian distribution N (0, I). Then ‖w (l) j,0‖2 ∼ χ2(ml−1). By Lemma 1 in Laurent & Massart (2000), we have with probability at least 1− e−ml−1 ,
‖w(l)j,0‖ 2 ≤ 5ml−1.
By union bound, we have with probability 1− 2(L+ 1)e−m/2 − e−ml−1 , the variance
aTj aj
m2l−1 ≤ 5C
2
ml−1
In the infinite network width limit m1, . . . ,ml−1 →∞, we see that the variance converges to 0 and the probability converges to 1.
B.1 PROOF OF LEMMA 3
Proof. First, note that∇α(l−1)(∇α(l−1))T can be decomposed as
∇α(l−1)(∇α(l−1))T = l−1∑ l′=1 ∇W (l′)α (l−1)(∇W (l′)α (l−1))T .
Then, its spectral norm can be bounded by
‖∇α(l−1)(∇α(l−1))T ‖ = ‖ l−1∑ l′=1 ∇W (l′)α (l−1)(∇W (l′)α (l−1))T ‖
≤ l−1∑ l′=1 ‖∇W (l′)α (l−1)(∇W (l′)α (l−1))T ‖ ≤ l−1∑ l′=1 ∥∥∥∥∥∥ ∂α (l′) ∂W (l′) l−1∏ l′′=l′+1 ∂α(l ′′) ∂α(l′′−1) ( ∂α(l ′) ∂W (l′) l−1∏ l′′=l′+1 ∂α(l ′′) ∂α(l′′−1)
)T∥∥∥∥∥∥ ≤
l−1∑ l′=1 ∥∥∥∥∥ ∂α(l ′) ∂W (l′) ∥∥∥∥∥ 2 l−1∏ l′′=l′+1 ∥∥∥∥∥ ∂α(l ′′) ∂α(l′′−1) ∥∥∥∥∥ 2 . (23)
In the following, we need to bound the terms ‖∂α(l′)/∂W (l′)‖ and ‖∂α(l′′)/∂α(l′′−1)‖. To simplify the presentation of the proof, we assume in the following that each network hidden layer has the same width m. We leave the general analysis for the readers.
We use the following lemma to bound the spectral norm of the weight matrices at initialization.
Lemma 4. If each component of W (l)0 , l ∈ [L], is i.i.d. drawn from N (0, 1), then with probability at least 1− 2e−m/2,
‖W (l)0 ‖ ≤ 3 √ m.
See the proof in Section B.2.
There is also a lemma that bounds the Euclidean norm of each hidden layer neuron vector α(l).
Lemma 5 (Modified Lemma F.3 of (Liu et al., 2020a)). There exists constants Cα, Bα > 0 such that, with probability at least 1− 2(L+ 1)e−m/2, for all l ∈ [L],
‖α(l)‖ ≤ Cα √ m+Bα. (24)
Using the above two lemmas, we can bounded those two terms. At initialization, we have, with probability at least 1− 2e−m/2,∥∥∥∥ ∂α(l)∂α(l−1) ∥∥∥∥2 = sup ‖v‖=1 1 m m∑ i=1 ( σ′(α̃ (l) i )W (l) 0,ijvj
)2 = sup ‖v‖=1 1 m ‖Σ′(l)W (l)0 v‖2
≤ 1 m ‖Σ′(l)‖2‖W (l)0 ‖2
≤ 9L2σ, and with probability at least 1− 2(L+ 1)e−m/2, for all l ∈ [L],∥∥∥∥ ∂α(l)∂W (l) ∥∥∥∥2 = sup ‖V ‖F=1 1 m m∑ i=1 (∑ j,j′ σ′(α̃ (l) i )α (l−1) j′ Ii=jVjj′
)2 = sup
‖V ‖F=1
1 m ‖Σ′(l)V α(l−1)‖2
≤ 1 m ‖Σ′(l)‖2‖α(l−1)‖2 ≤ L2σC2α + 1
m L2σB 2 α. (25)
Here Σ′(l) is a diagonal matrix, with the diagonal entry Σ′(l)ii = σ ′(α̃ (l) i ) and Lσ is the degree of Lipschitz continuity of the activation function σ(·). Now, using the above results, we can upper bound the spectral norm of the matrix ∇α(l−1)(∇α(l−1))T . With probability 1− 4(L+ 1)e−m/2, we have
‖∇α(l−1)(∇α(l−1))T ‖ ≤ l−1∑ l′=1 ∥∥∥∥∥ ∂α(l ′) ∂W (l′) ∥∥∥∥∥ 2 l−1∏ l′′=l′+1 ∥∥∥∥∥ ∂α(l ′′) ∂α(l′′−1) ∥∥∥∥∥ 2
≤ (l − 1)9l−1L2lσ (C2α + 1
m B2α). (26)
Since l ≤ L, we can see that, for sufficient large network width m, the spectral norm ‖∇α(l−1)(∇α(l−1))T ‖ is bounded by a constant.
B.2 PROOF OF LEMMA 4
Proof. Consider an arbitrary random matrix A ∈ Rma×mb with each entry Ai,j ∼ N (0, 1). By Corollary 5.35 of Vershynin (2010), for any t > 0, we have with probability at least 1− 2exp(− t 2
2 ),
‖A‖ ≤ √ ma + √ mb + t. (27)
For the initial neural network weight matrices, we have
‖W (1)0 ‖2 ≤ √ d+ √ m+ t, ‖W (l)0 ‖2 ≤ 2 √ m+ t, l ∈ {2, 3, ..., L},
‖W (L+1)0 ‖2 ≤ √ m+ 1 + t.
Letting t = √ m and noting that m > d, we finish the proof.
C INCLUDING w(l+1) AS PARAMETERS
Now, we consider the more general case where parameters in layer l + 1 are not fixed. Then, the quadratic term of the pre-activation α̃(l+1) is written as:
1 2 (θ − θ0)THα̃(l+1)(ξ)(θ − θ0)
= 1
2
( w(l+1) −w(l+1)0
θ(l) − θ(l)0
)T [ ∂2α̃(l+1) (∂w(l+1))2 (ξ) ∂ 2α̃(l+1) ∂θ(l)∂w(l+1) (ξ)
∂2α̃(l+1)
∂w(l+1)∂θ(l) (ξ) ∂
2α̃(l+1)
(∂θ(l))2 (ξ)
]( w(l+1) −w(l+1)0
θ(l) − θ(l)0
)
= 1
2 (w(l+1) −w(l+1)0 )T
∂2α̃(l+1)
(∂w(l+1))2 (ξ)(w(l+1) −w(l+1)0 ) (=: A)
+ 1
2 (θ(l) − θ(l)0 )T
∂2α̃(l+1) (∂θ(l))2 (ξ)(θ(l) − θ(l)0 ) (=: B)
+(w(l+1) −w(l+1)0 )T ∂2α̃(l+1)
∂w(l+1)∂θ(l) (ξ)(θ(l) − θ(l)0 ) (=: C)
where ξ is some point between θ0 and θ.
Note that α̃(l+1) is linear in w(l+1), hence, ∂ 2α̃(l+1)
(∂w(l+1))2 is always a zero matrix. Hence, term A ≡ 0.
Moreover, by Theorem 4, the term B becomes zero, as the width ml increases to infinity. For the term C, we note that
∂2α̃(l+1)
∂w(l+1)∂θ(l) = 1 √ ml ∇α(l).
Here, α(l) = (α(l)1 , . . . , α (l) ml) is the vector of the neurons in layer l and ∇α(l) is the matrix of the first-order derivative of the vector α(l). Using Lemma 3, we have an upper bound on the spectral norm: ‖∇α(l)‖ ≤ √ C, with C > 0 being a constant. Therefore, we have
|C| ≤ 1√ ml ‖w(l+1) −w(l+1)0 ‖‖∇α(l)‖‖θ(l) − θ (l) 0 ‖ ≤
R2 √ C
√ ml . (28)
In the limit of ml → ∞, term C converges to 0. Therefore, we have proved that each (l + 1)-th layer pre-activation α̃(l+1) has a vanishing quadratic term in its Taylor expansion Eq.(1), and hence becomes linear, in the limit of ml →∞.

heading: D DENSENET
text: In a DenseNet (Huang et al., 2017), a l-th layer neuron takes all previous layer neurons as inputs:
α(l) = σ(α̃(l)), α̃(l) = 1√ m W (l) ∗ Concat[α(l−1), . . . , α(1),x], (29)
where the “Concat” function concatenates all the vector arguments into a single long vector with m being the size, and ∗ is the matrix multiplication. The pre-activation can be viewed as the sum of l linear functions, α̃(l) = ∑l l′=1 α̃ (l′) U , where each α̃ (l′) U := 1√ m U (l ′)α(l ′) has a similar form as the pre-activation in full-connected neural network Eq.(8), but with parameters U (l ′) being a subset of W (l). Hence, using the analysis in Section 3, in the infinite network width limit and in O(1)neighborhoods of the initialization, each of the pre-activations of the DenseNet is a summation of l ≤ L linear functions, and hence is linear. Therefore, the DenseNet is also linear in O(1)neighborhoods of the initialization.

Review summaries:
This paper aims to explore what structural properties account for transition to linearity when a neural network becomes wider. The authors propose a new perspective where the neural network is considered as a multi-level assembly model. Each hidden layer can be viewed as an assembly model built up from a set of independent sub-models. Furthermore, they assume that the proposed assembly model is not dominated by a single or minor group of sub-models. This leads to neurons within the same hidden layer being independent when the network width grows to infinity, and to show that the network is linear in an O(1)-neighbourhood around the initialization.

Authors present a theoretical understanding for the "transition to linearity" phenomenon of wide neural networks with linear output layer under gradient descent. Presented line of thought develops from the perspective where one considers a neural network as a recursively-built assembly of sub-models which correspond to individual neurons from the preceding layers. Authors prove that the transition to linearity phenomenon when the number of sub-models converge to infinity (i.e., the network becomes wider) is a result of assembling weak sub-models that do not dominate the assembly from network initialization. 

This paper aims to explain the phenomenon that neural networks with infinite width tend to be linear in the neighborhood of initial optimization points, from an assemble model perspective. The key point is to prove that the quadratic term from Taylor expansion disappears when the width approaches infinity. The authors first proved in the simple two-layer case and then extend the results to deep neural networks with L layers.