Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This is a positive review. Feel free to skip to the feedback.

SUMMARY OF PAPER
This paper explains how to use cluster graphs to easily compute the asymptotic behaviour of any given correlation function (Definition 1) for deep linear networks. By "asymptotic behaviour" I mean that it upper-bounds correlation functions by c·n^s, where s is a nonnegative integer given by the particular cluster graph, and c a "constant" (which I think depends on the particular input, x, to correlation function, among other things).

The authors then conjecture (Conjecture 1) that these bounds transfer to deep nonlinear networks, and that they are tight:
- Appendix C proves that these upper bounds also hold for deep ReLU networks, and 1-hidden-layer networks with smooth nonlinearity. This is also mentioned in page 3.
- Section 2.3 empirically shows that these bounds are pretty tight. (in terms of the exponent, none of the theory here gives a value for the constant c)

The tool provided above is the main result. The authors then use it to provide some results about wide networks  
- They give a different proof that for large width, the Neural Tangent Kernel stays constant during training. This is because its derivative wrt. time as a function of width n is O(n^-1), and thus 0 for n->infinity.
- Using the ease of calculation from the tool, they approximate the change in the NTK over training time for any network. They do this using its value at initialization + a term that depends on n^-1. These results are numerically verified in Figure 1.
- They present numerical evidence for the accuracy of this approximation to the change in NTK over time. 

The authors spend the last 2 pages explaining how cluster graphs derive from Feynman diagrams (FDs), and why these help compute asymptotics.

WHY I AM ACCEPTING THIS PAPER

The paper adapts FDs and cluster graphs, which is a potentially very useful tool for other wide-network researchers, and could accelerate research in this whole sub-field. It also shows their power by providing a surprisingly large amount of novel theoretical results.

FEEDBACK

At a very high level, there is only one thing that I think isn't made quite clear by the presentation, and it should be. If I understand correctly, Feynman diagrams (or cluster graphs) are only used here to calculate correlation functions for deep *linear* networks. Then, other results establish that the width-dependent asymptotic behaviour for linear networks holds as-is for nonlinear networks, and these results with FDs constitute Conjecture 1. There are proofs for ReLU and 1-layer smooth networks, mentioned in pg. 3; and the experiments in the paper support it for common nonlinear deep networks as well. I think that asymptotics for linear networks transfer to nonlinear ones is an interesting result, which doesn't depend on FDs.

What follows are details.

It is unclear to me whether cluster graphs are as "powerful" as FDs, i.e. whether the bound at the end of the Proof in page 8 is always saturated. Are there some cases in which you need to use FDs to get a tighter upper bound?

In Table 1 you should say that the values under "lin. ReLU tanh" are the fitted exponent s_C. This is not explained. Perhaps you  can mark the only 2 cases (in the 5th row) where the bound is not tight. It would be nice to know how much error remains between the fitted c·n^(s_C) and the empirical values.

Please explain x1 <-> x2 in eq. 8

In figure 1b, consider adding the finite-width limit prediction for the training dynamics. You have already done so for the prediction of the NTK during training in figure 5c, you could indicate it in the same way in 5b.


Typos:

Figure 2 caption: feynman -> Feynman

pg 8. anlytic evicence -> analytic
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new tool based on Feynman diagrams to analyze wide networks (e.g., feed-forward networks with one or more large hidden layers or CNNs with a large number of filters).

The main contributions of the paper are:
- a new method (using Feynman diagrams) to bound the asymptotic behavior of correlation functions (ensemble averages of the network functions and its derivatives). The method is presented as a conjecture.
- tighter bounds for gradient flow of wide networks
- an extended analysis of SGD for wide networks
- a formalism for deriving finite-width corrections


The study of (infinitely) wide networks has been active over the last few years. A better understanding of wide networks could, amongst other things, shed light on recent empirical results related to over-parametrized networks.  As such, improving our theoretical understanding of wide networks and especially properties of finite-width networks, which is what this paper explores, seems significant and potentially very impactful.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper investigates the asymptotic behavior of correlation functions of wide networks. The main part of the work revolves around Conjecture 1 which assesses how the correlation function scales depending on the number of connected components of even/odd size of the constructed cluster graph. The authors then study training dynamics of wide networks under gradient flow and (stochastic) gradient descent and present empirical evidence to support their claims.

While I am no expert in this particular area, the paper is fairly well written and the main concepts and ideas are outlined nicely in most places. I do have some comments, though, wrt. the notation and the relevance of certain results:

(1) In 2.1. the authors state the def. of a deep LINEAR network, however, the activation functions are non-linear. Could you be more clear what you mean by linear in your setting? 

(2) What are the vertices in Conjecture 1? v_i = T(x_i), right? I think it's clear from the context (i.e., the definition of edges), but this could be written more precisely.

(3) What is the actual relevance of the ORDER of the correlation function in Conjecture 1 and the relevance of the cluster graph. Can the authors motivate this more clearly, or provide some more intuition on this construction?

(4) What does the notation x_1 \leftrightarrow x_2 in Eq. 8 mean?

(5) Thm. 3 - Apparently, the expression for C only depends on the #loops in \gamma. Is this independent of the number of connected components (especially, since Conjecture 1 explicitly hinges on #connected components)?

(6) Does the analysis equally hold if you consider affine maps (Ax + b ) instead of linear operations Ax? 

Overall, the paper presents some quite interesting results, but the authors could be more clear on the relevance of those results and its implications. Non-expert readers are left with having to figure this out on their own. In my point of view, this would make the paper much stronger.
review_title: Official Blind Review #3

Meta-review: This submission presents bounds on the training dynamics (including gradient evolution) for deep linear (and in some cases nonlinear) networks as a function of the width of the layers or number of convolutional layers. The work also presents experimental results that provide evidence that the bounds are tight.

Strengths:
The work provides interesting insights into these training dynamics, particularly for the wide-but-not-infinite setting, which is less studied.
The work also adapts cluster graphs and Feynman diagrams to derive these bounds, which could be useful tools for researchers in this field.

Weaknesses:
The validity and applicability of some of the results for nonlinear networks was not entirely clear at first but has been clarified in the revision.

The reviewer consensus was to accept this submission.

Decision: Accept (Spotlight)