Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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. 



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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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:

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

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

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

However, I can identify the following weaknesses in the paper, which I believe need to be addressed by the authors.

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

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

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

Overall, 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].

Reference:
[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.
questions: I have the following questions and suggestions to make to the authors:

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

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

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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

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

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

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

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

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

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

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

Second, 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
$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. 

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

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

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


A Minor point. Typo in Line 57: $\tilde O(1\sqrt m)$

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?

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

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

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

limitations: I did not sense any problem with honesty regarding limitations of this paper or potential ethical harms related to this paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: [Strength] The paper has the following strength.
- 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.
- The paper contextualizes well by offering reference to existing works and discussions.
- The paper provides a view from optimization of the loss via Polyak-Lojasiewicz theories which sees potential convergence rate arguments under the framework.
- The paper is well written overall except for the lack of experiments.

[Weakness] However, it has the following weakness which stops me from recommending the paper for publication in NeurIPS.
- 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.  
- 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).
questions: I would like to ask the following questions:
1. 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.
2. Would the constant in (12) depend on the c in Assumption 3.5?
limitations: See main review.
review_title: null

Meta-review: metareview: This is a challenging manuscript to make a final recommendation on accept or reject as there is a clear consensus amongst the reviewers that the manuscript is borderline between accept and reject.  The main concern is the incremental nature of the results, extending the prior results of Reference: [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. from fully connected networks to the more general setting of DAGs.  The authors and reviewers point out that the DAG setting requires substantial adaptation of the technique used to prove the results in [A] which is the reason I have selected Accept over Reject.  That said, the architecture the reviewers are most interested in is CNNs which were pointed out don't fall within the definition of the DAG and have been removed from the manuscript.  Inclusion of shared weights, CNNs, would be a great addition to the manuscript which would make the decision for acceptance clearer and would also make the manuscript more compelling for readers who otherwise are unsure the benefit of the DAG setting.
confidence: Less certain
Decision: Accept