Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies the finite depth and width corrections to the neural tangent kernel (NTK) in fully-connected ReLU networks. It gives sharp upper and lower bounds on the variance of NTK(x, x), which reveals an exponential dependence on a quantity beta=d/n, where d is depth, and n is hidden width. This implies that when beta is bounded away from 0, NTK(x, x) is not deterministic at initialization. The paper further analyzes the change of NTK(x, x) after one step of SGD on a single datapoint x, and shows that the change also depends exponentially on beta.

NTK has been a popular subject of theoretical study in deep learning, and it's an important question to understand when and to what extent NTK can capture the behavior of real neural networks. This paper makes partial progress by analyzing the diagonal entries of the NTK in fully-connected ReLU networks. It concludes that NTK(x, x) at initialization is not deterministic, and can change significantly after doing one SGD step on x, when beta is bounded away from 0. While it's nice that the authors obtained precise answers to these two questions, there are some drawbacks that limit the significance of this paper:

1. The entire paper only considers one single datapoint x, so it doesn't apply to the non-diagonal elements NTK(x, x') or the usual SGD with mini-batches containing multiple datapoints. Of course, it's already implied by the current paper that the NTK is not deterministic and can move a lot when beta is large, but it's unclear whether the reverse is true, i.e., what is the regime when the NTK becomes deterministic and frozen when an entire dataset is involved. An answer (even empirically) to this question would make the paper much more complete.

2. The result is also not so surprising given [Hanin, 2018] (and possibly some other papers by the same author) which also obtained a similar exp(beta) dependence using a similar combinatorial approach.

3. Minor issues regarding incorrect or missing references:
-- "Further, kernel method-based theorems show that even in this infinitely overparameterized regime neural networks will have non-vacuous guarantees on generalization (Wei et al., 2018)." The result of Wei et al. is not about kernel method and in particular not NTK.
-- "In fact, empirically, networks with finite but large width trained with initially large learning rates often outperform NTK predictions at infinite width." The authors should refer to the work of [Arora et al., 2019] which AFAIK is the first paper that provides empirical study of the (convolutional) NTK predictor at infinite width on relatively large datasets like CIFAR-10.

[Hanin, 2018] Which Neural Net Architectures Give Rise to Exploding and Vanishing Gradients?
[Arora et al., 2019] On Exact Computation with an Infinitely Wide Neural Net


--------
update: Thanks to the authors for the detailed reply, which answers most of my questions. I am updating my rating to weak accept in light of this.

Regarding Wei et al.: Their result on NTK is negative, i.e., they aimed to show that NTK is inferior to regularized NN. I find the way you cited this paper a bit weird. 
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The paper investigates a novel infinite width limit taking depth to infinite at the same time. This is beyond conventional theoretical studies for infinite width networks where depth is kept finite when the width is taken to be infinite. The main object that paper studies is the neural tangent kernel which is of great interest to the theoretical deep learning community as it describes gradient descent dynamics in a tractable way.

While standard NTK becomes deterministic in the infinite width limit, when both depth and width are simultaneously taken to infinity this paper shows that NTK is no longer deterministic. Moreover authors show that gradient descent update induce non-negligible change to the Kernel. 

There are two main limitations of otherwise significant work. One is generality of sums over path method used here beyond ReLU/Fully connected/single input setting. It is a very powerful technique allowing tight upper and lower bound for variation of diagonal entry of NTK. I worry that the method may be too specific to the particular network setting. Still this does not eclipse the strong results it could say for ReLU networks. 

Second limitation is lack of empirical check. I understand it may be non-trivial to simulate double scaling limit and theoretical contribution alone could be significant progress. I still believe that empirical support should be a strong foundation of science of neural networks and this paper would improve even with some toy model implication of simultaneous depth/width limit. One might particularly wonder, for sufficiently deep/wide network that we could train on our computer, can we observe effects of d/n ( or \sum_i  1/n_i)?

Question:
I did not quite comprehend the alluded connection to double descent curve with data-dependent features in section 3.2. Could you elaborate?

nit : Dyer&Gur-Ari’s workshop paper is from the 2019 ICML workshop instead of 2018. 
p3 sentence below eq (5) unnecessary ‘them’ in the end of line.    

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: This is an important contribution to understand finite depth and width corrections to the NTK. The authors show that the diagonal terms of NTK remain stochastic when depth and width approach infinity at the same rate. 

NTK [1] is one of the most exciting discovers for extremely over-parameterized NNs in the last year. In the single limit setting, i.e. fixing depth and letting width -> infinity, the [1] showed that the NTK converges in distribution to a deterministic kernel and remained almost unchanged during gradient descent.  This regime is known as the kernel regime or linearized regime, where the training dynamics of the NN is well-approximated by its first order Taylor expansion. 

In this paper, the authors show that in the double limit regime, i.e. depth/width = \beta and depth, width -> infinity, the diagonal terms of the NTK, as well as the first gradient step, is NOT deterministic. More precisely, they upper and lower bound the second moment of the diagonal terms of NTK (and first gradient step) through the temperature \beta. Their method builds on the `"sum-over-path approach" developed in [3], etc. 

Overall, this is a very interesting result, proposing a new scaling limit that gradient descent dynamics can be highly nontrivial (i.e. not in the kernel regime.) and NNs can possibly learn useful representation. 

Other comments: 
1. It will be very helpful to have some experiments to support the main theorems in the paper since the proof is quite involved. 
2. How difficult is it to compute the off-diagonals? Is it possible to obtain other statistics of of the NTK, trace, max eigenvalue, etc. 
3. Is it possible to extend the results to other non-linearities, e.g. Tanh? 


[1]Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- ´
eralization in neural networks. In Advances in neural information processing systems, pp. 8571–
8580, 2018.
[2] Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient
descent. arXiv preprint arXiv:1902.06720, 2019.
[3]Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture.
In Advances in Neural Information Processing Systems, pp. 571–581, 2018
review_title: Official Blind Review #3

Meta-review: This paper aims to study the mean and variance of the neural tangent kernel (NTK) in a randomly initialized ReLU network. The purpose is to understand the regime where the width and depth go to infinity together with a fixed ratio. The paper does not have a lot of numerical experiments to test the mathematical conclusions. In the discussion the reviewers concurred that the paper is interesting and has nice results but raised important points regarding the fact that only the diagonal elements are studied. This I think is the major limitation of this paper. Another issue raised was lack of experimental work validating the theory. Despite the limitations discussed above, overall I think this is an interesting and important area as it sheds light on how to move beyond the NTK regime. I also think studying this limit is very important to better understanding of neural network training. I recommend acceptance to ICLR.
Decision: Accept (Spotlight)