Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper presents an approach for going beyond NTK regime, namely the linear Taylor approximation for network function. By employing the idea of randomization this paper manages to reduce the magnitude of the linear part while the quadratic part is unaffected. This technique enables further analysis of both the optimization and generalization based on the nice property of quadratic approximation.

I believe this paper should be accepted because of its novel approach to go beyond the linear part, which I view as a main contribution. Also, this paper is well written and presents its optimization result and proof in a clear manner. Although it is an innovation in the theoretical perspective, I still want to raise two questions about the object this paper trying to analyze:

1. The activation function is designed so that it has really nice property: it has second-order derivative which is lipshitz. Actually I believe Assumption A is first motivated by cubic ReLU. Why is cubic ReLU so favorable in this paper? Is it possible to use quadratic ReLU in the proof? Also I wonder what is the key property of activation function which is allowed here.

2. The network model considered here, is modified to a randomized neural network. So maybe this paper just circumvents the difficulty in going beyond NTK regime? I have this concern because in reality optimizing this network model seems intractable. To evaluate the loss $L(\mathbf{W})$ or $L_{\lambda}(\mathbf{W})$ we take expectation over $\Sigma$; when doing gradient descent, apparently the gradient also takes exponential time to compute.

Overall, I believe this paper has high quality and I enjoyed reading it. However, I do expect response from authors which could address my concerns raised above. This can help me achieve a better understanding and a more precise evaluation on this paper.

***

I have read the author's response and decide to remain the rating as weak accept.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper investigates higher order Taylor expansion of NTK (neural tangent kernel) beyond the linear term. The motivation of this study is to investigate the significant performance gap between NTK and deep neural network learning. The conventional NTK analysis only deals with the first order term of the Taylor expansion of the nonlinear activation, but this paper deals with higher order terms. In particular, it thoroughly investigates the second order expansion. It is theoretically shown that the expected risk can be approximated by the quadratic approximation, and show that the optimal solution under a quadratic approximation can achieve nice generalization error under some conditions.

Overall, I think the analysis interesting. Actually, there are big gap between NTK and real deep learning. However, this gap is not well clarified from theoretical view points. This is one of such attempts.
As far as I understand the analysis is solid. The writing is clear. I could easily understand the motivation and the results. The quadratic expansion is clearly different from the recent series of NTK analyses. In that sense, this study has sufficient novelty.

On the other hand, I think the study has several limitations. My concerns are summarized as follows:
- The proposed objective function is different from the normal objective function used for naive SGD because there is a "random initialization" term and some special regularization terms. Therefore, the analysis in this paper does not give precise understanding on what is going on for the naive SGD in deep learning.
- As far as I checked, there is no definition of OPT. Is it the optimal value of \tilde{L}(W)? Since OPT is an important quantity, this must be clarified.
- L^Q(W) considers essentially a quadratic model, and is different from the original model. It is unclear how expressive the quadratic model is. Since the region where the quadratic model is meaningful is restricted (i.e., ||w_r|| = O(m^{-1/4}) is imposed), the expressive power of the model in this regime is not obvious. It is nice if there are comments on how large its expressive power is. In particular, it is informative if sufficient conditions for L^Q(W_*) <= OPT is clarified.
- (This comment is related to the right above comment) There are two examples in which the linear NTK is outperformed by the quadratic model. However, they are rather simple. It would be better if there was more general (and practically useful) characterization so that there appears difference between the two regimes.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies the training of over-parameterized neural networks. Specifically, the authors propose a novel method to study the training beyond the neural tangent kernel regime by randomizing the network and eliminating the effect of the first order term in the network’s Taylor expansion. Both optimization guarantee and generalization error bounds are established for the proposed method. It is also shown that when learning polynomials, the proposed randomized networks outperforms NTK by a factor of d, where d is the input dimension. 

Overall, I enjoy reading this paper. The presentation is clear, the arguments are insightful, and the proofs seem to be solid. Moreover, this paper offers some interesting ideas to show that neural networks can outperform NTK, which might be impactful. However, this paper also has certain weak points, mainly due to the less common problem setting. 

Although it is believed that NTK cannot fully explain the success of deep learning, results in the NTK regime have the advantage that the problem setting (initialization method, training algorithm) is very close to what people do in practice. Therefore, ideally, a result beyond NTK should demonstrate the advantage of NN over NTK under similar, or at least practical settings. If the problem setting is changed in some strange way, then it might not be that meaningful even if the training behavior is different from the NTK setting. In my opinion, the following four points about the problem setting in this paper are less desired:

(1) Assumption A is not satisfied by any commonly used activation functions. The authors only provided cubic ReLU as an example.

(2) The randomization technique in this paper is not standard, and is pretty much an artifact to make the first order term in the Taylor expansion of neural networks small.

(3) The $(\| \cdot \|_{2,4})^8$ regularization term introduced on page 6 is highly unusual. Due to reparameterization, this regularization is on the distance towards initialization, indead of the norms of the weight parameters.

(4) The training algorithm used in this paper is noisy SGD due to the need to escape from saddle points.

Despite the issues mentioned above, I still think this paper is of good quality, and these limitations are understandable considering the difficulty to escape from the NTK regime. It would be interesting if the authors could provide some direct comparison between the generalization bound in this submission and existing generalization bounds in the NTK regime, for example the results in

Yuan Cao, Quanquan Gu, Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
Yuan Cao, Quanquan Gu, Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

Moreover, since this paper studies optimization with regularization on the distance towards initialization, it would also be nice to compare with the following paper:

Wei Hu, Zhiyuan Li, Dingli Yu, Understanding Generalization of Deep Neural Networks Trained with Noisy Labels 

review_title: Official Blind Review #1

Meta-review: This paper studies the training of over-parameterized two-layer neural networks by considering high-order Taylor approximation, and randomizing the network to remove the first order term in the network’s Taylor expansion. This enables the neural network training go beyond the recently so-called neural tangent kernel (NTK) regime. The authors also established the optimization landscape, generalization error and expressive power results under the proposed analysis framework. They showed that when learning polynomials, the proposed randomized networks with quadratic Taylor approximation outperform standard NTK by a factor of the input dimension. This is a very nice work, and provides a new perspective on NTK and beyond. All reviewers are in support of accepting this paper. 
Decision: Accept (Poster)