Transition to Linearity of General Neural Networks with Directed Acyclic Graph Architecture
Authors: Libin Zhu
Chaoyue Liu
Misha Belkin
Venue: NeurIPS 2022 Accept (2022)
Keywords: wide neural networks
directed acyclic graph
transition to linearity
neural tangent kernel
over-parameterization

Abstract: In this paper we show that feedforward neural networks corresponding to arbitrary directed acyclic graphs undergo transition to linearity as their ``width'' approaches infinity. The width of these general networks is characterized by the minimum in-degree of their neurons, except for the input and first layers. Our results identify the mathematical structure underlying transition to linearity and generalize a number of recent works aimed at characterizing transition to linearity or constancy of the Neural Tangent Kernel for standard architectures. 

Transition to Linearity of General Neural Networks with Directed Acyclic Graph Architecture
Libin Zhu'
Chaoyue Liut
Mikhail Belkin
Abstract
In this paper we show that feedforward neural networks corresponding to arbitrary directed acyclic graphs undergo transition linearity their "width" approaches infinity. The width of these general networks is characterized by the minimum in- degree of their neurons, except for the imput and first layers. Our results identify the mathematical structure underlying transition to linearity and generalize number of recent works aimed at characterizing transition to linearity or constancy of the Neural Tangent Kernel for standard architectures.
Introduction
A remarkable property of wide neural networks, first discovered in [10] in terms of the constancy of the Neural Tangent Kernel along the optimization path, is that they transition linearity (using the terminology from [14]), i.e., are approximately linear in a ball of fixed radius. There has been an extensive study of this phenomenon for different types of standard neural networks architectures including fully-connected neural networks (FCNs), convolutional neural networks (CNNs), ResNets [12, 4, 3, 7J. Yet the scope of the transition to linearity and the underlying mathematical structure has not been made completely clear.
In this paper, we show that the property of transition to linearity holds for a much broader class of neural networks - feedforward neural networks. The architecture of feedforward neural network can generically be described by DAG [25, 24, 16]: the vertices and the edges correspond the neurons and the trainable weight parameters of a neural network, respectively. This DAG structure includes standard network architectures e.g., FCNs, CNNs, ResNets, as well as DenseNets [9], whose property of transition to linearity has not been studied in literature. This generalization shows that the transition to linearity, or the constant Neural Tangent Kernel, does not depend on the specific designs of the networks, and is more fundamental and universal property.
We define the width of feedforward neural network as the minimum in-degree of all neurons except for the input and first layers, which is a natural generalization of the the minimum number of neurons in hidden layers which is how the width is defined for standard architectures. For feedforward neural network, we show it transitions to linearity if its width goes to infinity as long as the in in-degrees of individual neurons are bounded by a polynomial of the network width. Specifically, we control the deviation of the network function from its linear approximation by the spectral norm of the Hessian of the network function, which, as we show vanishes in a ball of fixed radius, in the infinite width limit. Interestingly, we observe that not only the output neurons, but any pre-activated neuron in the hidden layers of a feedforward neural network can be regarded as a function with respect to its parameters, which will also transition to linearity as the width goes to infinity.
DDepartment of Computer Science & Halicioğlu Data Science Institute, University of California, San Diego.
E-mail: 16zhu@uesd. edu "aliiioglu Data Science Institute. University of California, San Diego. E-mail: ch12120ucsd. edu I Haliccoglu Data Science Institute. University Californi, San Diego. E-mail: abelkin@ucsd. edu
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The key technical difficulty is that all existing analyses for transition to linearity or constant NTK do not upply this general DAG setting. Specifically, those analyses assume in in-degrees of neurons are either the same or proportional to each other up to a constant ratio [5, 12, 3, 26, 14, 2]. However, the general DAG setting allows different scales of neuron in-degrees, for example, the largest in-degree can be polynomially large in the smallest in-degree. In such scenarios, the (2, 2, 1) - in [14] and the norm of parameter change in [5, 12] scales with the maximum of in-degrees which causes trivial bound on the NTK change. Instead, we introduce a different set of tools based on the tail bound for the norm of matrix Gaussian series [22]. Specifically, we show that the Hessian of the network function takes the form of matrix Gaussian series, whose matrix variance relies on the Hessian of connected neurons. Therefore, we reconcile the in-degree difference by building a recursive relation between the Hessian of neurons, which exactly cancels out the in-degree with the scaling factor.
Transition to linearity helps understand the training dynamics of wide neural networks and plays an important role in developing the optimization theory for them, as has been shown for certain particular wide neural networks [6, 5, 4, 12, 27, 26]. While transition to linearity is not necessary condition for successful optimization, it provides powerful tool for analyzing optimization for many different architectures. Specifically, transition to linearity in a ball of sufficient radius combined with lower bound on the norm of the gradient at its center is sufficient to demonstrate the PL* condition [13] (a version of the of optimization. We discuss this connection and provide one such lower bound in Section 4.
condition [19, 15]) which ensures convergence
Summary of contributions. We show the phenomenon of transition to linearity in general feed- forward neural networks corresponding a DAG with large in-degree. Specifically, under the assumption that the maximum in-degree of its neurons is bounded by a polynomial of the width m (the minimum in-degree), we prove that the spectral norm of the Hessian of a feedforward neural network is bounded by ((L/vm) in an ((1) ball. Our results generalize the existing literature on the lincarity of wide feedforward neural networks. We discuss connections to optimization. Under additional assumptions we show that the norm of the gradient of a feedforward neural network is bounded away from zero at initialization. Together with the Hessian bound this implies convergence of gradient descent for the loss function.
1.1 Notations
We use bold lowercase letters, e.g., to denote vectors, capital letters, e.g., A, to denote matrices, and bold capital letters, e.g., H, to denote higher order tensors or matrix tuples. For a matrix A, we use AR..) to denote its i-th row and A to denote its j-th column.
We use /wo/(w)) to denote the gradient of / with respect to w at Wo. and H,(w) to denote Hessian matrix (second derivative) of I with respect w. For vectors, we use || || to denote Euclidean norm. For matrices, we use || || to denote spectral norm and || || to denote Frobenius norm. We use ||- Iloo to denote function Lo norm. For a set S, we use |S| denote the cardinality of the set. For n > 0, [n] denotes the set 21, n...
We use big-O notation to hide constant factors, and use big-Ô notation to additionally hide logarithmic factors. In this paper, the argument of O1Ō(.) is always with respect to the network width.
Given a vector w and a constant R > 0, we define a Euclidean ball B B(w, R) as:
B(w, R) == {v: ||v -wl < R}
(1)
2 Neural networks with acyelic graph architecture
In this section, we provide definition and notation for general feedforward neural networks with an arbitrary DAG structure. This definition includes standard feedforward neural network architectures. such as FCNs, DenseNet and CNNs.
2.1 Defining feedforward neural networks
Graph Structure. Consider directed acyclic graph (DAG) G = (V,E), where V and & denote the sets of vertices and edges, respectively. See the left panel of Figure for an illustrative example.

---

Layer 2
Layer (Output)
Layer
U3
e2
1/2
Layer
(11, V3
Layer 0 (Input)
U1
(a)
(b)
Figure (a): An example of directed acyelic graph. 01, 02 and Uy are three vertices and 61 62 are two edges of the graph. va has two incoming edges e and e2 which connects to ei and v2 respectively. (b): Organizing the vertices into layers. The vertices with 0 in-degree are in 0-th layer (or input layer), and last layer are called output layer in which the vertices have 0 out-degree, Note that the layer index determined by the longest path from the inputs Vinput for example, the neuron in layer 3.
For directed edge &, we may also use the notation e (V1, U2) to explicitly write out the start vertex and end vertex
For vertex V, we denote its in-degree, in(v). by the number of incoming edges (edges that end with it):
in(v) [n)),), with (n) == {u E V: (u, B) E}.
Similarly, for vertex E V, we denote its out-degree out(v) by the number of outgoing edges (edges that start from it):
out(u) = (Suu(()), with Sout (v) {u V (v, E E).
We call the set vertices with zero in-degrees input: Vinput = {0 E V: in(v) = 0}, and the set of vertices with zero out-degrees output Voutput {e E V out(r) 03.
Definition 2.1. For each vertex V V(Vipput its distance p(v). to the input Vinput. is defined to be the maximum length of all paths that start from vertex within Vipput and end with v.
It is easy to check that p(v) = 0 if v Vinput-
Feedforward neural network. Based on given DAG architecture, define the feedforward neural network. Each individual vertex corresponds to a neuron additionally equipped with a scalar function (also called activation function). Each edge associated with a real-valued weight, a trainable parameter. Each neuron is defined as a function of the weight parameters and the adjacent neurons connected by its incoming edges. The feedforward neural network is considered the output neurons, corresponding to the output Voutput, of all weight parameters and input neurons which correspond to the input Vinput. Formally, we define the feedforward neural network follows.
Definition 2.2 (Feedforward neural network). Consider DAG g (V,E). For each vertex v E V Vinpat we associate it with an activation function a.(()) : R - R and each of its incoming edges (u,v) E with weight variable w. W(a,))- Then we define the following functions:
fo f==o(fo). f.
Σ
W(a,o)fu.
Vin(u) (ESi(())
When v E Vinput= fo prefixed as the input data, and we denote Sinput == (fo : Vinput For E Vinput, we call fo nearons and f. pre-uctivations. With necessary composition of functions, each for and for can be regarded feedforward neural network is defined to be the function corresponding to the output Voutput
function of all related weight variables and inputs fimput The
f(W: finpat) foutput {ffo Voutput)
(3)
where W = (we+ E E) denotes the set of all the weight variables.
3

---

Remark 2.3. The validity of the definition is guaranteed by the fact that the DAG is acyelic. It makes sure that the dependence of each function fo on other neurons can pass all the way down to the imput Sinpat, through Eq. (2). Remark 2.4. For Vinput Voutput. we use the identity function Il()) as the activation functions.
Weight initialization and inputs. Each weight parameter we W is initialized i.i.d. following the standard normal distribution i.e., (00, 1). The inputs are considered given, usually determined by datasets. Under this initialization, we introduce the scaling factor 1/ /i(()) in Eq. (5) to control the value of neurons to be of order O(1). Note that this initialization an extension of the NTK initialization [10], which was defined for FCNs therein.
Generality of DAG architecture. Including FCNs and DenseNets [9] as special examples, the class of feedforward neural networks allows much more choices of architectures, for example, neural networks with randomly dropped edges. Please see detailed discussions about these specific examples in Appendix We note that our definition of feedforward neural networks does not directly include networks with nont-trainable skip connections, e.g., ResNets, and networks with shared weights, e.g., CNNs. However, with a slight modification of the analysis, the property of transition to linearity still holds. See the detailed discussion in Appendix D and E.
2.2 Organizing feedforward networks into layers
The architecture of the feedforward neural network is determined by the DAG G. The complex structures of DAGs often lead to complicated neural networks, which are hard to analyze.
For the ease of analysis, we organize the neurons of the feedforward neural network into layers, which are sets of neurons.
Definition 2.5 (Layers). Consider a feedforward neural network f and its corresponding graph structure G. A layer of the network is defined to be the set of neurons which have the same distance p to the inputs. Specifically, the Ł-th layer, denoted by f(() is
( = {fo : p(v) = E, u EVEEEN
(4)
is easy to see that the layers are mutually exclusive, and the layer index é is labeled from 0 to f, where L + 1 the total number of layers in the network. As p(u) 0 if and only if u E Vimput. the O-th layer f(0) is exactly the input layer finput- The right panel of Figure 1 provides an illustrative example of the layer structures.
In general, the output neurons foutput (defined in Eq. (3)) do not have be in the same layer. For the convenience of presentation and analysis, we assume that all the output neurons are in the last layer, i.e., layer f, which is the case for most of commonly used neural networks, e.g., FCNs and CNNs. Indeed, our analysis applies to every output neuron (see Theorem 3.8), even if they are not in the same layer.
With the notion of network layers, we rewrite the neuron functions Eq, (2), as well as related notations, to reflect the layer information.
For ê-layer, 0, 1,..... L. we denote the total number of neurons as de, and rewrite the layer function (()) into form of vector-valued function
f( (1 1(0
122)
where we use f((9) with index i = 1, 2, .de to denote each individual neuron. Correspondingly,
and we denote its vertex as (2))) and S((0) = S.n (v. (7) Hence, the in-degree in(v(")) ), denoted as m
here, is equivalent to the cardinality of the set S.
Remark 2.6. Note that m() with the superscript É, denotes an in-degree, i.e., the number of neurons that serve as direct inputs to the current neuron in E-th layer. In the context of FCNs, m," (2) is equivalent
to the size of its previous layer, i.c., (f- 1)-th layer, and is often denoted as m ((-1) in literature.

---

To write the summation in Eq. (2) as matrix multiplication, we further introduce the following two vectors: (a), sب represents the vector that consists of neuron components fo with ( (b),
w! represents the vector that consists of weight parameters " "((,,(") with E S Note that both vectors 550 and w; have the same dimension m;
With the above notation, the neuron functions Eq. (2) can be equivalently rewritten as:
1. o. (2) (f( 1.0
T
55(0--
(5)
Vm (8)
For any & E [Z]. we denote the weight parameters corresponding all incoming edges toward neurons at layer by
= ((
E [L].
(6)
Through the way define the feedforward neural network, the output of the neural network is function of all the weight parameters and the input data, hence we denote by
f(w; = f(0 = (n1 1 r2l)",
(7)
where w the collection of all the weight parameters, i.e., w == ((w())T,..,, (w()()))))))) RE, E, m
With all the notations, for a feedforward neural network, we formally define the width of it: Definition 2.7 (Network width). The width m of a feedforward neural network the minimum in-degree of all the neurons except those in the input and first layers:
inf
EE(2.....),.EEIu,) [E(de)
Remark 2.8. Note that, the network width m determined by the in-degrees of neurons except for the input and first layers, and not necessarily relates the number of neurons in hidden layers. But for certain architectures e.g., FCNs, these two coincide that the minimum in-degree after the first layer the same as the minimum hidden layer size.
We say a feedforward neural network is wide if its width m is large enough. In this paper, we consider wide feedforward neural networks with fixed number of layers.
3 Transition to linearity of feedforward neural networks
In this section, we show that the feedforward neural networks exhibit the phenomenon of transition linearity, which was previously observed in specific types of neural networks.
Specifically, we prove that a feedforward neural network f(w; æ)), when considered as a function of its weight parameters is arbitrarily close linear function in the ball B(wo, R) given constant R > 0, where Wo is randomly initialized, as long as the width of the network sufficiently large.
First, we make the following assumptions the input æ and the activation functions:
Assumption 3.1. The input is uniformly upper bounded, i.e., ||0/|/o S Cv for some constant C2. Assumption 3.2. All the activation functions a+-) twice differentiable, and there exist constants To, 7, ?22 > 0 such that, for all activation functions, (a( I % and the following Lipschitz continuity and smoothness conditions satisfied
[o'(21) - o' (=2)) S 71/21 - #2),
(2"(2)) o" S 22/21 221. V2n, 22
R.
We note that the above two assumptions are very common in literature. Although ReLU does not satisfy Assumption 3.2 due to non-difierentiabiiiy at point 0, we believe our main claims still hold as ReL.U can be approximated arbitrarily closely by some differentiable function which satisfies our assumption.
5

---

Remark 3.3. By assuming all the activation functions are twice differentiable, it is not hard to see that the feedforward neural network i.e., Eq. (7) is also twice differentiable.
Taylor expansion. To study the linearity of general feedforward neural network, we consider its Taylor expansion with second order Lagrange remainder term, Given a point Wo, we can write the network function f(w) (omitting the input argument for simplicity) as
f(w)- (wo) + (w - wo) (wwwo) / (wo)) + (w- wo)
wwww) H(y(())) wo),
fiin (w)
R(w)
where Ç is a point on the line segment between wo and w. Above, flin is a linear function and R(w) is the Lagrange remainder term.
In the rest of the section, we will show that in ball B( o R) of any constant radius R > 0,
[[(w] [
(10)
where is the network width (see Definition 2.7). Hence, f(w) can be arbitrarily close to its linear approximation fin (w) (w) the network function. The same analysis can be applied to multiple outputs (see Corollary C.1).
with sufficiently large m. Note that in Eq. (9), we consider a single output of
Remark 3.4. For a general function, the remainder term R(w) is not expected to vanish a finite distance from We. Hence, the transition to linearity in the ball B (W. Rt) is a non-trivial property. On the other hand, the radius R can be set to be large enough contain the whole optimization path of GD/SGD for various types of wide neural networks (see [13, 27]. also indicated in [6, 26, 12]). In Section 4, we will see that such a ball is also large enough to cover the whole optimization path of GD/SGD for the general feedforward neural networks. Hence, to study the optimization dynamics of wide feedforward neural networks, this ball is large enough.
To prove Eq. (10), make assumption on the width m: Assumption 3.5. The maximum in-degree of any neuron is at most polynomial in the network width m:
sup EE (((d)) m O(m)),
where e is a constant.
This assumption puts a constraint on the neurons with large in-degrees such that the in-degrees cannot be super-polynomiall large compared to m. A natural question is whether this constraint is necessary, for example, do our main results still hold in cases some in-degrees are exponentially large in m?? While we believe the answer is positive, we need this assumption to apply the proof techniques. Specifically, we apply the tail bound for the norm of matrix Gaussian series [22]. where there is dimension factor equivalent to the number of weight parameters. Thus an exponentially large dimension factor would result in useless bounds. It is still an open question whether the dimension factor in the bound can be removed or moderated (see the discussion after Theorem 4.1.1 in [22]).
With these assumptions, we are ready to present our main result:
Theorem 3.6 (Scaling of the Hessian norm). Suppose Assumption 3.1, 3.2 and 3.5 hold. Given fixed R O, for all w B(wo, R),, with probability at least exp(-S(log" m)) over the random initialization Wo, each output neuron fa of a feefforward neural network satisfies
[ = =0 (logm + R))² //m) = =ō ( Wm). (n)) E [dee.
(1I)
This theorem states that the Hessian matrix, as the second derivative with respect weight parameters w, of any output neuron can be arbitrarily small, if the network width is sufficient large.
Note that Eq. (11) holds for all E B(w,, R) with high probability over the random initialization Wo- The basic idea is that, the spectral norm of Hessian can be bounded at the center of the ball, i.e., Wo. though probability bounds due to the randomness of we- For all other points w B(Wo, R), the distance |[ woll. being no greater than R, controls [J((W) ) H (wo)]l such that it is no larger than the order of || H (wo)ll I]. hence || (w)]l keeps the same order. See the proof details in Subsection 3.1.
Using the Taylor expansion Eq. (9), we can bound the Lagrange remainder and have transition to lincarity of the network:

---

f (W; x))
Experimental result
Max Relative Change NTK
0.20
Thecrectical prediction
0.15
0.10
0.05
0.00
160
1000
Layer
Figure 2: Transition to linearity of DAG net- work. The experimental result approximates well the theoretical prediction of relative change of tangent kernel from initialization to conver- gence, as function of the network width. Each point on the solid curve is the average of inde- pendent 5 runs.
Figure 3: An example of DAG network with bottleneck neurons. The DAG network x(W; has two bottleneck neurons (in red dashed circles) with in-degree 1, while the rest neurons except for the input and the first layer have large in-degree. In this case, f(W; as) will still transition to linearity with respect to W as the number of neurons goes to infinity.
Corollary 3.7 (Transition to linearity). Suppose Assumption 3.1, 3.2 and 3.5 hold. Given fixed R > 0, for all w E B(wo, R), with probability at least exp(-[((log' m)) over the random initialization wo, each fu will be closely approximated by linear model:
Ifa(w) - (w))l(()]
1
sup wzB(ww.
[ (w) = +2
For feedforward neural networks with multiple output neurons, the property of transition to linearity holds with high probability, if the number of output neurons is bounded, i.e., di ( See the result in Appendix C.
Furthermore, as defined in Definition 2.2, each pre-activation, as a function of all related weight parameters and inputs, can be viewed feedforward neural network. Therefore, we can apply the same techniques used for Theorem 3.6 to show that each pre-activation can transition to linearity:
Theorem 3.8. Suppose Assumption 3.1, 3.2 and 3.5 hold. Given a fixed radius R > 0, for all w E B(wo, R), with probability at least - exp((S((log) m)) over the random initliazation of wo. any pre-octivation in a feedforward neural network i.e., f(() (w) satisfies
EE [L]. 1 [de]- Re (w) =0 (logm Bogm++H R) //mm = = /vmm
(12)
Remark 3.9. Note that pre-activations in the input layer i.e., the input data and the first layer are constant and linear functions respectively, hence the spectral norm of their Hessian is zero.
Experimental verification. To verify our theoretical result on the scaling of the Hessian norm, i.e., Theorem 3.6, we train DAG network built from 3-layer DenseNet with each weight removed i.i.d. with probability 1/2, on 10 data points of CIFAR-2 (2-class subset of CIFAR-10 [1 [I] using GD. We compute the maximum relative change of the tangent kernel (definition is deferred to Eq. (17)) during training, i.e., max, Kr Koll/1 /|| Koll to simulate the scaling of the spectral norm of the Hessian. We
observe the convergence of loss for all widths (2, 2 .... 212), }, and the scaling of the Hessian follows close to the theoretical prediction of ((1/ /m). See Figure 2.
Non-linear activation on output neurons breaks transition to linearity. In the above discussions, the transition to linearity of networks are under the assumption of identity activation function on every output neuron. In fact, the activation function on output neurons critical to the linearity of neural networks. Simply, composing non-linear function with linear function will break the linearity. Consistently, as shown in [13] for FCNs, with non-linear activation function on the output, transition to lincarity does not hold any more.
7

---

"Bottleneck neurons" do not necessarily break transition to linearity. We have seen that if all neurons have sufficiently large in-degree, the network will transition to linearity. Does transition to linearity still hold, if neurons with small in-degree exist? We call neurons with small in-degree bottleneck neurons, as their in-degrees are smaller than rest of neurons hence forming "bottlenecks". As we show in Appendix E, existence of these bottleneck neurons does not break the transition to linearity, as long as the number of such neurons is significantly smaller than that of non-bottleneck neurons. Figure 3 shows example with two bottleneck neurons, whose in-degree is 1. This network still transitions to linearity as the number of neurons goes to infinity.
3.1 Proof sketch of Theorem 3.6
By Lemma K.I. the spectral norm of ft can be bounded by the summation of the spectral norm of
all the Hessian blocks, i.e., ||H ll S Ee, & || where ((().a)) := iw aw Therefore, it suffices to bound the spectral norm of each block. Without lose of generality, we consider the block with 1 S 4 S E2 S L.
8² fz
By the chain rule of derivatives, we can write the Hessian block into:
fe
Σ de
pF!!
0fk ol
EGh L.e
(13)
Ow(t))ww(e)
(w(())w(())
Pmfa
For each GLit" since ,! =0 (F(!t)
again by the chain rule of derivatives, we have
def
ff Ow dw(ti)@((ta (22)
0 F2
of
of(())
G
(w())
(2)
o"
(L)
id
Owllij
Ow(ts)
V
Σ
w
o'
(F!r)) Gree"
(1)
id
m r=
affee T (wi(ta)
Σ
o" (I!(e)
(14)
(L)
i
Ow((1))
m
us! EF s(1)
P where F F(( = (s: f E f s and id = {p: (1S{2),, = -!
The first quantity on the RHS of the above equation, Σ (w (1) idt
o' (F. G. is a matrix
Gaussian series with respect to random variables (L) k conditioned on fixed o' (f(*) op for all i such that ((()) E F sto We apply the tail bound for matrix Gaussian series, Theorem 4. 4.1.1 from [22], to bound this quantity. To that end, we need to bound its matrix variance, which suffices to bound the spectral norm of Σ; G. since o'()) is assumed to be uniformly bounded by Assumption 3.2. There a recursive relation that the norm bound of G.-.!' depends on the norm bound of G. which appears in the matrix variance. Therefore, we can recursively apply the argument to bound each G.
Similarly, the second quantity on the RHS of the above equation also a matrix Gaussian series with T
(L) respect to w k conditioned on fixed o" (F!
a
for all i such that f (e") E F F5(
DwiFT
As o(() is assumed to be uniformly bounded by Assumption 3.2, we use Lemma B. to bound its matrix variance. hence the matrix Gaussian series can be bounded.
Note that such tail bound does not scale with the largest in-degree of the networks, since the in-degree of [k. i.e., m (L) will be cancelled out with the scaling factor 1/ 1/vmz(()
(D) in the bound of matrix variance.
See the complete proof in Appendix B.
8

---

Relation to optimization
While transition to linearity is significant and surprising property of wide networks in its right, it also plays an important role in building the optimization theory of wide feedforward neural networks. Specifically, transition linearity provides path toward showing that the corresponding loss function satisfies the PL* condition in a ball of a certain radius, which is sufficient for exponential convergence of optimization to global minimum by gradient descent or SGD [13].
Consider a supervised learning task. Given training inputs and labels { 9:) y:) we use GD/SGD to minimize the square loss:
1 (.(::a)))- -;)²,
((w)=
(15)
2 i=1
where fw: is a feedforward neural network.
The loss [(w) is said to satisfy j-PLL" condition, a variant of the well-known Polyak- Lojasiewii condition [19, 15], point w, if
|V WV)((()) 2uC(w), p >
Satisfaction of this prP condition in ball B(wo, R) with R O(1/p) around the starting point Wo of GD/SGD guarantees a fast converge of the algorithm to global minimum in this ball [13].
In the following, use the transition to linearity of wide feedforward networks to establish the PL* condition for L(w). Taking derivative on Eq. (15), we get
V L(w)l? 2 2Amin (K(w))
(16)
where matrix K(w), with elements
Key(w)= = [wf(ww::;) V fw(;)) for i,j E [na].
(17)
called Neural Tangent Kernel (NTK) [10], and Amiu (-) denotes the smallest eigenvalue of matrix. Note that, by definition, the NTK matrix is always positive semi-definite, i.e., Amin (aann((())) (Kw)) 2 0.
Directly by the definition of PI." condition, at given point w, if Amin AminnK (K(w) is strictly positive, then the loss function L(w) satisfies PI." condition.
To establish convergence of GD/SGD, it sufficient to verify that PL* condition is satisfied in a ball B(wo, R) with R = O(1pu). Assuming that Amin (K (wo)) is bounded away from zero, transition to linearity extends the satisfaction of the PL* condition from one point Wa to all points in B(wo, R).
PL* condition at Wa- For certain neural networks, e.g., FCNs, CNNs and ResNets, strict positive- ness of Amin K (Wo)) can be shown, for example, [6, 5]. We expect same holds more generally, in the case of general feedforward neural networks. Here we show that Amiu (K (K(w)) (wo)) can be bounded from for one data point under certain additional assumptions. Since there is only one data point, Amin (K( (wo)) = K (wo) = V (2o) We also assume the following on activation functions and the input.
Assumption 4.1. The input x satisfies x ~ Ia.).
Assumption 4.2. The activation function is homogencous, i.c ((2) = a" ( >> 0 for any constant a. And infre((-1),ie(4)) 12 o (=) C. 0.
Remark 4.3. Here for simplicity we assume the activation functions are homogeneous with the same It not hard to extend the result the case that each activation function has different r. Proposition 4.4. With Assumption 4.1 and 4.2, we have for any l E [dæ).
2 min 1,, min Co 1SSLL
>111 Co ) 2(1)
Ex
[|
(18)
The proof can be found in Appendix G.
The above proposition establishes a positive lower bound on /Vo)((o))), hence also on Amin (K(wo) Using Eq. (16), we get that the loss function L(w) satisfies PL at wo-

---

Extending PL" condition to (wwu, R). Now we use transition to linearity to extend the satisfaction of PL" condition the ball B(wo, R). In Theorem 3.6, we see that, feedforward neural network f(w) transitions to linearity, i.c., (w)] = ((1/ vm) in this ball. An immediate consequence is that, for any w B( RR,
Dmiia (K(w) Amin ( (K()))) S
sup
[
weB(wo,
Since Amin Amin( (W())) is bound from and [w)) can be arbitrarily small as long as m is large enough, we have Amia (K( (w)) is lower bounded from 0 in the whole ball. Specifically, there is > such that
inf (t)
Amin (K(w) J..
Moreover, the radius R can be set to be (1//u), while keeping the above inequality hold. Then, applying the theory in [13], existence of global minima of L(w) and convergence of GD/SGD can be established.
For the case of multiple data points, extra techniques are needed to lower bound the minimum eigenvalue of the tangent kernel. Since we focus more on the transition to linearity of feedforward neural networks in this paper, we leave it as a future work.
Non-linear activation function outputs and transition to linearity. In this paper, we mainly discussed feedforward neural networks with linear activation function on output neurons. most of the literature also considers this setting [10, 17, 18, 6, 27,7, 26]. In fact, as pointed out in [13] for FCNs, while this linearity of activation function on the outputs is necessary for transition linearity, it is not required for successful optimization. Specifically, simply adding nonlinear activation function on the output layer causes the Hessian norm to be (1), independently of the network width. Thus transition to linearity does not occur. However, the corresponding square loss can still satisfy the PL condition and the existence of global minimum and efficient optimization can still be established.
Discussion and future directions
In this work, we showed that transition to linearity arises in general feedforward neural networks with arbitrary DAG architectures, extending previous results for standard architectures [10, 12, 14]. We identified the minimum in-degree of all neurons except for the input and first layers the key quantity to control the transition to linearity of general feedforward neural networks.
We showed that the property of transition to linearity is flexible to the choice of the neuron function Eq. (2). For example, skip connections Eq. (30) and shared weights Eq, (32) do not break the property. Therefore, we believe our framework can be extended to more complicated neuron functions, e.g., attention layers [8]. For non-feedforward networks, such as RNN, recent work [1] showed that they also have constant NTK. For this reason, expect transition to linearity also to occur for of non-fcedforward networks.
Another direction of future work is better understanding of optimization for DAG networks, which requires more delicate analysis of the NTK at initialization. Specifically, with multiple training examples, a lower bound on the minimum eigenvalue of the NTK of the DAG networks is sufficient for the PL condition to hold, thus guaranteeing the convergence of GD/SGD.
Acknowledgements
We are grateful for support of the NSF and the Simons Foundation for the Collaboration the Theoretical Foundations of Deep Learning through awards DMS-2031882 2031883 and #814639. We also acknowledge NSF support through IIS-1815697 and the TILOS institute (NSF CCF-21 12665). We thank Nvidia for the donation of GPUs. This work used the Extreme Science and Engineering Discovery Environment (XSEDE, [21]). which is supported by National Science Foundation grant number ACI-1548562 and allocation TIG-CIS101044.
"https:// "actps::/deeppoundatiooss a1/
10

---

References
[1] Sina Alemohammad, Zichao Wang. Randall Balestriero, and Richard Baraniuk. "The Recurrent Neural Tangent Kernel". In: International Conference on Learning Representations. 2020.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-paramettrriztion"" In: International Conference on Machine Leurning. PMLR. 2019, pp. 242-252.
[3] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. "On Exact Computation with an Infinitely Wide Neural Net". In: Advances in Neural Information Processing Systems 32 (2019), pp. 8141-8888 81500
[4] Lenaic Chizat, Edouard Oyallon, and Francis Bach. "On lazy training in differentiable pro- gramming". In: Advances in Neural Information Processing Systems 32 (2019).
[5] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. "Gradient Descent Finds Global Minima of Deep Neural Networks". In: International Conference on Machine Learning. 2019, Pp. 1675-1685.
[6] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. "Gradient Descent Provably Optimizes ever-parameterized Neural Networks". In: International Conference on Learning Representations. 2018.
[7] Boris Hanin and Mihai Nica. "Finite Depth and Width Corrections to the Neural Tangent Kernel". In: International Conference on Learning Representations. 2019.
[8] Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. "Infinite attention: NNGP and NTK for deep attention networks". In: International Conference Machine Learning.
PMLR. 2020, pp. 4376-4386.
[9] 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 pattern recognition. 2017, pp. 4700-4708.
[10] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural tangent kemel: Convergence and generalization in neural networks". In: Advances in neural information processing systems. 2018. pp. 1571-8580.
[11] Alex Krizhevsky, Geoffrey Hinton, et al. "Learning multiple layers of features from tiny images". In: (2009).
[12] Jaehoon Lee, Lechao Xiao, Samuel Schoenbolz, Yasaman Bahri, Roman Novak, Jaseha Sohl- Dickstein, and Jeffrey Pennington. "Wide neural networks of any depth evolve linear models under gradient descent". In: Advances in neural information processing systems 32 (2019), pp. 8572-8583.
[13] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. "Loss landscapes and optimization in over- parameterized non-linear systems and neural networks". In: Applied and Computational Harmonic Analysis (2022).
[14] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. "On the linearity of large non-linear models: when and why the tangent kernel is constant", In: Advances in Neural Information Processing Systems 33 (2020).
[15] Stanislaw Lojasiewiez. "A topological property of real analytic subsets". In: Coll. du CNRS. Les équations aux dérivées partielles 117 (1963), pp. 87-89.
[16] James L McClelland, David E Rumelhart, PDP Research Group, et al. Parallel Distributed Processing, Volume 2: Explorations in the Microstructure of Cognition: Psychological and Biological Models. Vol. 2. MIT press, 1987.
[17] Andrea Montanari and Yiqiao Zhong. "The interpolation phase transition in neural networks: Memorization and generalization under lazy training". In: arXiv preprint arXiv:2007. / (2020).
[18] Quynh Nguyen, Marco Mondelli, and Guido F Montufar. "Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks". In: International Conference on Machine Learning. PMLR. 2021, pp. 8119-8129.
[19] Boris Teodorovich Polyak. "Gradient methods for minimizing functionals". In: Zhurnal Vy- chislitel' noi Matematiki i Matematicheskoi Fiziki 3.4 (1963), pp. 643-653.
[20] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. "Dropout: a simple way to prevent neural networks from overfitting". In: The journal of machine learning research 15.1 (2014), pp. 1929-1958.

---

[21] J. Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, D. Peterson, Roskies, J. R. Scott, and N. Wilkins-Diehn "XSEDE: Accelerating Scientific Discovery". In: Computing in Science & Engineering 16.5 (2014), pp- 62-74. ISSN: 1521-9615. DOI: 10. 1109/ (009/MMSE... 2014. 80. URL: doi www.ccmmpteesooccee...........ee org/ /0. 10.
1109/MCSE. 2014.002440 80.
[22] Joel A Tropp et al. "An Introduction Matrix Concentration Inequalities", In: Foundations
and Trends@ in Machine Learning 8.1-2 (2015), pp. 1-230.
[23] Roman Vershynin. High-diiensiooal probability: An introduction with applications in data
science. Vol. 47. Cambridge university press, 2018.
[24] Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. "Discovering neural wirings". In:
Advances in Neural Information Processing Systems 32 (2019).
[25] Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. "Graph structure neural net- works". In: International Conference on Machine Learning. PMLR. 2020, pp. 10881-10891.
[26] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. "Gradient descent optimizes parameterized deep ReLU networks". In: Machine Learning 109.3 (2020), pp. 467-492.
[27] Difan Zou and Quanquan Gu. "An improved analysis of training over-parameterized deep neural networks". In: Advances in Neural Information Processing Systems. 2019, pp. 2053- 2062.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] This is a paper with theoretical results hence the assumptions constitute the core limitations. We have the discussion for each assumption.
(c) Did you discuss any potential negative socictal impacts of your work? [No] The work presents mathematical results related to deep learning and is not expected to have any negative societal impact within its scope.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assumption 3.1, 3.2 and 3.5.
(b) Did you include complete proofs of all theoretical results? [Yes] We give proof sketch in Section 3.1 and the complete proofs can be found in appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pJiipIBRbrV", "reviewer": "Reviewer_vWFG", "summary": "In the \"NTK\" regime, the behavior of a neural network becomes similar to a linear model (i.e., the first-order approximation at initialization) when the network width approaches infinity. This has been established by many authors under standard architectures such as fully-connected and convolutional neural networks.\n\nThis paper considers feed-forward networks that can be represented as directed acyclic graphs (DAGs), which is an extension of existing feed-forward architectures such as fully-connected networks, convolutional networks, densenet, etc.\n\nDefining the minimum in-degree (# of edges coming into a node) as the \"width\" $m$, the paper shows that the Hessian of the network function decays as $O(1/\\sqrt{m})$ under the standard NTK parameterization, which implies that the network becomes similar to a linear approximation around its initialization as $m \\to \\infty$. \n\nSuch an observation leads to consequences in optimization: If the minimum eigenvalue of the NTK kernel matrix is bounded away from zero at initialization, then linear convergence to a global minimum can be implied.\n", "questions": "Q1. In the main results, there is the radius constant $R > 0$. The result seems to hold for any $R$, so it is natural to expect to see some dependence on $R$ appearing in the theorem statement. However, as it is stated in the paper, $R$ does not show up both in the spectral norm and the probability. This seems unnatural to me and I think there should be some $R$ hiding in the $O$ notation. What is the exact dependency on $R$ in the theorem statements?\n\nQ2. In (8), why do you take the maximum up to $L-1$? Does it mean that we ignore the in-degrees of output neurons? However, in Line 164 it is stated that \"except input and first layers\".\n\nQ3. In line 193, it is stated that: \"Here we assume the output dimension of the network function is one. The same analysis can be applied to multiple outputs\". However, the main theorems are handling each of the multiple output neurons albeit separately. This is confusing. \n\nQ4. I don't understand the equations below line 256. Here, $\\ell'$ is supposed to be anything between $\\ell_2$ and $L$ inclusive. However, it seems to me that in the 2nd terms of RHS (the ones that involve $\\sigma''$), $\\ell'$ is acting as if $\\ell' = L-1$, the last hidden layer? Correct me if I'm mistaken.\n", "limitations": "I did not sense any problem with honesty regarding limitations of this paper or potential ethical harms related to this paper.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1. This paper extends the well-known NTK phenomenon to general feed-forward networks which can be represented by DAGs. This is a nontrivial thing to do, and they have apparently used advanced mathematical tools to achieve this (although I didn't have the time to check the proof).\n\nW1. While I value the amount of effort put into proving these results, I have to say that the main results and their implications are somewhat exactly as expected. In [4], it was already proved for general smoothly parameterized models that increasing the scale $\\alpha$ of the model leads to lazy training (i.e., NTK regime) where the training dynamics becomes similar to the first-order approximation at initialization. As mentioned in [4], for neural networks with NTK parameterization, increasing width $m$ corresponds to increasing the scale $\\alpha$, hence we can expect a similar \"linearization\" behavior regardless of the network's architecture (except that the output layer has to have identity activation). For this reason, my impression of this paper is that the new insights provided by this paper are somewhat limited. Please correct me if I am mistaken.\n\nW2. While the authors claim that the DAG formulation includes many popular architectures like CNN, ResNet, and Dropout, there is a caveat; I believe that DAG formulation as described in Section 2.1 does NOT include any of them properly. Again, please correct me if I am wrong, I would be happy to change my view.\n\nFirst, it doesn't include CNN because the formulation does not carefully handle shared weights. The authors claim in Appendix A that their results continue to hold for such shared weights and I think this would be the case, but such dependencies must be handled with great care. \n\nSecond, since the formulation assigns weights to each edge, the formulation cannot include connections without tunable weights (i.e., identity skip connections in ResNets). The authors claim in Appendix D that they handle skip connections by considering a network of the form\n$f_v = \\sigma_v(\\tilde f_v) + \\tilde f_v$, but this is nothing but redefining the activation function $\\sigma_v \\to \\sigma_v + Id$! A proper \"ResNet\" must be of the form $f_v = \\Phi(f_u) + f_u$ where $\\Phi$ contains some neural network layers, NOT a single pass through an activation function. \n\nThird, Dropout drops some of the neurons during training, which can be perfectly modeled with this DAG formulation. However, what I'm concerned about is its dynamic nature; throughout training, different sets of neurons get dropped and put back to the architecture. I wonder if this DAG formulation is capable of modeling and handling such a stochastic and dynamic nature of Dropout layers.\n\nW3. Partly due to the DAG structure, the paper has very confusing notation. My overall impression is that we are not gaining much out of this additional confusion.\n\nThroughout, I got very confused about the output layer index $\\ell$ or $L$. Stated in line 138, the output layer is layer $\\ell$, but $\\ell$ is also frequently used to index different lines. Also, if the network has depth $L$, shouldn't the output layer be $L$, the last layer? This already suggests that the paper could use more polishing, in terms of its clarity/writing.\n\n\nA Minor point. Typo in Line 57: $\\tilde O(1\\sqrt m)$\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F_FXbMVqMcb", "reviewer": "Reviewer_wXUj", "summary": "This paper extend the results on transition of neural networks to linear regime as width grows to Directed Acyclic Graph (DAG) architectures that include almost all of the feedforward networks and networks with dropout. Then based on properties of the linear regime, the authors prove such wide neural networks satisfy the Polyak-Lojasiewicz conditions, that guarantees the convergence of GD/SGD to global minima.", "questions": "Is your results in section 4 ( Relation to optimization) only for MSE loss? can it be extended to other looses? ", "limitations": "Unfortunately, the authors do no provide any experiments to support their theorems. I believe this should be added to the paper.  ", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper extend the current results on linearity of wide MLPs to almost all feedforward neural networks. The idea is not original, but the techniques and theorems that are provided in this paper can be interesting to the Neurips community. Also the paper is very well-written. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "3fNLGp9L5Eu", "reviewer": "Reviewer_gBNf", "summary": "This paper shows that feedforward neural networks, defined as those whose neurons and their corresponding connections form a Directed Acyclic Graph (DAG) satisfy the transition to linearity property, as their width increases. The authors prove this property for this class of neural networks and show how it can be used to demonstrate exponential convergence of GD and SGD.", "questions": "I have the following questions and suggestions to make to the authors:\n\n- In the paper, it is stated that ResNets do not fall under the examined architecture, but I am having difficulty understanding why (given that they only correspond to skipping some layers and do not add circles in the architecture). I would appreciate if the authors could clarify this.\n\n- Given the great number of notation used in this work, I would suggest the authors gather the symbols used in a table in the appendix, so it can be referenced easily.\n", "limitations": "The authors adequately adress the limitations of their work (namely, the fact that they consider only a particular class of networks, and that the all of the neurons need to have similar in-degree), and I do not think further discussion on this is necessary.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a purely theoretical work, demonstrating some interesting properties for a very general class of neural networks. Its main strengths lie in the following:\n\n- The authors clearly present the main theoretical contributions of the work, as well as their corresponding limitations. Reading the paper, it is very clear what the authors aim to prove (namely, that the class of neural networks they examine becomes arbitrarily close to linear functions, as their width increases).\n\n- The authors also prove how the above property can be used to show that GD and SGD converge fast for this class of networks, which is a useful guarantee from an optimization perspective.\n\n- The paper is also theoretically sound. The proof sketches in the main paper are clear, and I did not find any major issues with the full proofs included in the appendix. As such, the main claims of the paper are properly supported.\n\nHowever, I can identify the following weaknesses in the paper, which I believe need to be addressed by the authors.\n\n- First, I am somewhat unsure about the novelty of the setting examined by the paper. The properties proposed are similar to those obtained in a previous paper cited by the authors [A]. The major difference lies in that this work considers a general DAG architecture, while the previous one examines a more constrained fully connected architecture (which constrains the edges between the neurons to be strictly from a previous layer to a later one, while in this work the more general DAG structure allows for back-edges, as long as no cycle is formed). This is because the neurons are arranged in layers based on their distance from the input, so there can be a longer path to a neuron in an early layer which also goes through a later layer. However, it seems to me that the DAG architecture can be converted to that of the previous work by splitting the edges of the network, increasing the distance of neurons from the input, and given that there are no cycles in the graph this process must terminate with a more traditional feedforward network (where all edges go from early layers to later ones). Hence, it seems to me that graphs with a general DAG structure can be converted to an equivalent network corresponding to a regular feedforward network. I would appreciate it if the authors could comment on whether the above is a correct understanding of the architecture they examine, as well as further elaborate on the differences of their work from [A].\n\n- Secondly, the results of the authors consider R (the radius of the ball within which the linear approximation holds) to be a constant, and thus omit it from their results. I believe that this should be included in the result – the quality of the linear approximation with respect to the distance from the origin of the ball is important, in my opinion, to fully understand differences from simple linear approximation via Taylor expansion.\n\n- Finally, while the theoretical part of the paper is strong, I feel that in its current state the authors do not adequately motivate its ramifications. There is a direct application to GD and SGD, but this is made clear only in Section 4. I believe that furthering the discussion on the application of these results would help the paper. In a similar vein (while obviously not necessary, given the theoretical nature of the paper), I believe that a simple visual example of the transition to linearity would help with the presentation of the paper.\n\nOverall, I believe this is a good theoretical work, and I lean towards acceptance, especially if the authors further clarify the relationship of their work with [A].\n\nReference:\n[A]: Liu, C., Zhu, L., & Belkin, M. (2022). Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59, 85-116.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0nO0qM2hPv", "reviewer": "Reviewer_wA2n", "summary": "The paper extends the key result from the neural tangent kernel on the transition to linearity as width of dense neural networks grows to infinity and shows that feedforward neural networks that can be captured as directed acyclic graphs exhibit similar property captured by large in-degree. The results in the paper are more general than existing ones on transition to linearity. The paper gives theoretical justifications for the results but is lacking on the empirical aspects.", "questions": "I would like to ask the following questions:\n1. How does the result actually apply to CNN, ResNets, and DenseNets that the author claims? May consider adding related experiments (may be simple) for this in the next revision.\n2. Would the constant in (12) depend on the c in Assumption 3.5?", "limitations": "See main review.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength] The paper has the following strength.\n- The paper works on top of the neural tangent kernel and extends its key property of transition to linearity under infinite width to more general network structures captured by directed acyclic graphs, which is a more general result from existing ones.\n- The paper contextualizes well by offering reference to existing works and discussions.\n- The paper provides a view from optimization of the loss via Polyak-Lojasiewicz theories which sees potential convergence rate arguments under the framework.\n- The paper is well written overall except for the lack of experiments.\n\n[Weakness] However, it has the following weakness which stops me from recommending the paper for publication in NeurIPS.\n- The paper has focused solely on theoretical justifications and offers limited empirical evidence. Though I agree the overall atmosphere in the community focusing on empirical evidence may be detrimental, but I still believe carefully designed experiments would enable a wider audience to understand the work better (myself included). For example, the claims on linearity for the DAG-captured networks can be empirically shown like the experiments in the original neural tangent kernel paper.  \n- The scope of the work is incremental in its nature by extending the property of transition to linearity to other explicit neural networks. I am very curious on whether these results extend to attention based structures and implicit models. Though the reviewer fully recognizes that the difficulty would be very high in this direction (already considerable as presented, the reviewer believes, not related to the incremental nature).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept