Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This paper analyzed the expressive power of kernels by studying the reproducing kernel Hilbert space (RKHS) associated with the kernels. Specifically, the authors analyzed the eigenvalue decays in terms of the power series expansions of the kernel function around some points, which is related to the RKHS of the kernel. This analysis can be used to recover some previous results. Besides, using this analysis, the authors have shown several interesting results, including that NTK (which corresponds to fully-connected ReLU networks with infinite width, small learning rate, and proper initialization) with any depth has the same RKHS. The main result also has other corollaries about other kinds of kernels, e.g., Laplace kernel and infinitely differentiable kernels. Experiments were done to validate the theoretical results on synthetic datasets and MNIST/Fashion-MNIST.

Pros:

1. Analyzing the role of depth in deep neural networks is a very important problem, and people observed empirically depth separation phenomena, i.e., deeper networks have more expressive power. The authors analyzed this problem and showed that NTK constrained to the unit sphere does not have the depth separation phenomenon, which makes this paper interesting.

2. The authors did experiments in a nice way to validate the theoretical results. They did experiments on both synthetic datasets and real datasets, compare different kernels and repeat the experiments multiple times.

3. The experimental methodologies and theoretical computations appear to be correct.

Cons:

1. As mentioned by the authors, there is a recent concurrent work (Chen & Xu, 2020) that also obtains the result that NTK with any depth have the same RKHS, but the authors did not provide enough comparisons to that work. It would be better if a more detailed comparison can be provided.

2. The experiments are only done on synthetic datasets/MNIST/Fashion-MNIST with RF/NTK. It would be more convincing if the authors could do experiments with more kernels (e.g., Laplace kernel) or on larger datasets (e.g., CIFAR).

Recommendation:

I tend to vote for accepting this paper. The main reason is that the problem analyzed in this paper is important, and the results in this paper are interesting and kind of surprising. It showed the limitations of NTK in explaining the depth separation phenomenon, which could give people more insights and understandings about NTK.

Supporting arguments for recommendation:

See "Pros", especially point 1 there.

Questions for the authors:

Please address the cons mentioned above.

Additional feedback:

The lines in Figure 1 are a bit hard to distinguish, and it would be better to plot it more clearly, e.g., somehow separate the lines farther away.
review_title: Interesting improvement in analyzing expressive power of kernels

final_score: rating: 6: Marginally above acceptance threshold
review_content: -------------- Overview of the paper ----------------

The paper establishes the similarity between kernels (random feature kernel and neural tangent kernel) induced by shallow neural networks and deep ones. In particular, the approximation power is analyzed through the eigenvalue decay of the corresponding kernels --- shallow and deep networks share the same order of decay, expect the difference in parity and constants.

-------------- Contribution and strength ----------------

The message of the paper tends to be a negative perspective on viewing overparameterized neural networks as kernels, which motivates a surge of recent works on showing overparameterized neural networks are easy to optimize and generalize as well as kernels. Yet viewing neural networks as kernels cannot explain the advantage of neural networks, and leaves a large gap between the established theory and practice. This paper, provides theoretical justifications of the insufficiency of the kernel view point.

The organization of the paper is clear and it is relatively easy to read through, although some background on kernels and overparameterized neural networks are needed. Given the tight page limit, the paper makes a good balance between introductory materials and theoretical results.

Theoretically results appear to be correct and sound.

-------------- Weakness ----------------

The data distribution is a bit restricted. However, this is acceptable for later explicit computations of the eigenfunctions and eigenvalues (spherical harmonics and gegenbauer polynomials). Is it possible to consider more general data distributions?

-------------- Questions ----------------

1. The main result (theorem 1) asserts the expansion of the kernel around point 1 and -1. Is it an artifact of the proof (in order to apply integration by part)? Or it in fact reveals some interesting facts on distinguishing identical and orthogonal data points?

2. In Figure 1, we see 2-layer outperforms other models. This is not covered in the proposed theory --- any intuitions on its connection to Theorem 1? Meanwhile, the network width in ReLU random features experiment is smaller than the sample size, which is not the standard overparameterization discussed in lazy training regime. Can the authors elaborate on the choice of the network width?


review_title: Similarity between kernels induced by shallow and deep neural networks; Eigenvalue decay

final_score: rating: 7: Good paper, accept
review_content: The paper shows that the kernel derived from deep fully-connected networks on the sphere have the same approximation properties as their two-layer counterpart for ReLU activations. This implies the limitations of the kernel framework for studying the benefits of such deep networks. The authors derive the asymptotic eigenvalue decay of dot-product kernels from differentiability properties of the kernel function.

Overall, I vote for accepting. The paper is overall well-written and has a solid contribution. It addresses the limitation of the kernel framework, which is very interesting and phenomenal. The experiments are clear to illustrate the theory.

Some concerns are as follows:

The paper only considers ReLU activations and step activations (Section 3.3). Can the analyses be generalized to other network architectures? 

The proof only analyzes the kernels on the sphere. It seems hard to generalize the proof to other larger region like R^d. The extension seems to be limited from my side.

Some related literature are missing. To name a few:
Z. Fan and Z. Wang. Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks (2020).
A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the similarity between the laplace and neural tangent kernels (2020).
Y. Cao, Z. Fang, Y. Wu, D.-X. Zhou, and Q. Gu. Towards understanding the spectral bias of deep learning (2019).
Y. Cho and L. K. Saul. Kernel methods for deep learning (2009). 



review_title: Recommendation to accept on "Deep Equals Shallow for ReLU Networks in Kernel Regimes"

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: 
Recently, there are a large number of deep learning theory papers related to the property of neural tangent kernel. This paper shows that for ReLU, the kernels derived from deep fully-connected networks have the same approx. properties as their shallow two-layer counterpart. This highlights the limitation of the kernel framework for understanding the benefits of deep networks from such perspective.

I really like the idea of this paper. This paper is very well-written. I verified the proofs, it looks correct. I think this paper should be clearly accepted. 

Here are some minor comments about references.

In page 1, several references should be added into NTK literature

Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.
Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks (ICML)

Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. (NeurIPS)

Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. (NeurIPS)

Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein. Training (Overparametrized) Neural Networks in Near-Linear Time. (ITCS)

Zhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound.

In page 6, there is a section talking about ''finite neuron case''. It might be reason to slightly mention about ''infinite neuron case''. The work by Arora et al and Lee et al, shows a connection between infinite case and (ridge) kernel regression.

Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. (NeurIPS)

Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. (NeurIPS) 

review_title: A nice result in the field of NTK and deep learning

Meta-review: This paper analyzes the expressive power of NTK corresponding to deep neural network. It is shown that the depth hardly affects the behavior of the spectrum of the corresponding integral operator, which indicates that depth separation does not occur as long as NTK is considered.
The analysis is novel and gives a significant insight to the NTK research literature. The theoretical framework considered in this paper is considerably broad and potentially can be applied to several types of activation functions (while only ReLU is analyzed as a concrete example in the paper). Moreover, some numerical experiments are conducted that support the validity of the theoretical analysis. 
All reviewers are positive on this paper. I agree with their evaluations. For these reasons, I think this paper is worth acceptance.
Decision: Accept (Poster)