Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The goal of this paper is to complete the theoretical subset inclusion relationships given in (Geifman et al., 2020).
The authors proved that the RKHS of the the neural tangent kernel (NTK) with any number of layers
is a subset of the RKHS of the Laplace kernel.
Combined with the results in (Geifman et al., 2020),
if the input domain is restricted to the sphere of $(d-1)$-dimensional real space,
the RKHS of NTK with any number of layers
is equal to the RKHS of the Laplace kernel.

The writing of this paper is very clear.
I can easily get what the authors intend to express.
However, I still have some doubts about the details.

In Section 2.1,
the original Laplace kernels and exponential power kernels are all classic shift-invariant kernels.
Here the authors provided the dot-product versions of these two kernels.
Why do the authors need to do these changes?
For the sphere $\mathbb{S}^{d-1}$, the shift-invariant versions are equivalent to the dot-product kernels?

Under Lemma 3,
if $\Sigma_k(x, x) = 1$,
we can only get $\Sigma_k(u) = \Sigma_{k-1}(u)$.
What does the notation $\kappa_1^{(k)}$ means here?

Theorem 1 in (Aronszajn, 1950, p. 354) just stated that if $K_1 \preccurlyeq K_2$, then $\mathcal{K}_1 \subseteq \mathcal{K}_2$.
I am very curious and doubting about Lemma 4.
For any positive constant $\gamma > 0$,
does Lemma 4 always exist?

Under Lemma 4, the authors stated that:
1. "Then the Maclaurin series of $K_{\mathrm{Lap}}(u)$ and $N_k(u)$ have all non-negative coefficients by the classical approximation theory."
2. "If the Maclaurin series of $K(u)$ have all non-negative coefficients,
$K$ is a positive definite kernel on the unit sphere.

I cannot find the original documents of (Schoenberg, 1942) and (Cheney and Light, 2009).
Could you please provide these results in the Appendix such that we can check the correctness of these results?
This is because, in the following part, all the proofs will be focused on $\gamma^{2}\left[z^{n}\right] K_{\text {Lap }}(z) \geq\left[z^{n}\right] N_{k}(z)$.

In Section 3,
I have two doubting points.
1. The first one is under the definition of $\Delta$-domain.
The authors used $z$ to replace $u$ and $u=x^{\top} y$ as shown Section 2.1.
If we put $u=x^{\top} y = 1$,
the Laplace kernels and exponential power kernels given in Section 2.1 will all become constant.
Could the authors explain more about this assumption?
2. The second one is under Lemma 5.
The authors stated that "Careful singularity analysis then gives ...".
It is very difficult for me to easily get these two results about Maclaurin coefficients.
Could you give the detailed steps for the derivation of these results?

In Theorem 2,
I am very curious about the seemingly contrary results:
$\mathcal{H}_{K_{\text {exp }}^{\gamma_1, \sigma_1}} \left(\mathbb{S}^{d-1}\right) \subseteq \mathcal{H}_{K_{\text {exp }}^{\gamma_2, \sigma_2}}\left(\mathbb{S}^{d-1}\right)$, and 
$\mathcal{H}_{K_{\mathrm{exp}}^{\gamma_2, \sigma_2}}\left(\mathbb{R}^{d}\right) \subseteq \mathcal{H}_{K_{\mathrm{exp}}^{\gamma_1, \sigma_1}}\left(\mathbb{R}^{d}\right).$
Could you provide more explanations about this point in Section 4.
The superficial explanations cannot help us understand this point.
We need to go deeper into the proof sketch to figure out what makes this phenomenon happen.

I didn't go much deeper into the Appendix,
so it is hard for me to check the correctness of the whole paper.
Since ICLR is a highly selective conference,
I will give a score 5 at present.
After the authors solved my concerns and other reviewers verifies the correctness of all proofs,
I may raise my score to 6 or 7.
review_title: A clearly written paper but I still have some doubts

final_score: rating: 7: Good paper, accept
review_content: This paper compares the reproducing kernel Hilbert spaces (RKHSes) generated by a deep neural tangent kernel (NTK), a Laplacian kernel, and an exponential power kernel. The main result is twofold: 1) the RKHSes associated with a NTK and a Laplacian kernel  contain the same set of functions when restricted to the sphere S^{d-1}; and 2) the RKHS generated by the exponential kernel with a smaller power contains more functions when restricted to the sphere S^{d-1} or R^d.

The key proof idea involves an analysis  the asymptotic rates of the Maclaurin coefficients of the kernels. Aronszajn’s lemma is then used to establish the inclusion of the RKHS. A notable contribution in the proof is the application of analytic combinatorics to obtain the asymptotic rate O(n^{-3/2}) of the Maclaurin coefficients of the NTK which is intractable due to its recursive definition.  The authors also provide numerical results showing the empirical rate matches the theoretical asymptotic rate of the Maclaurin coefficients of the Laplace kernel and NTKs.

Overall, I think the paper is well-written, and the proof is solid.  The proof technique using analytic combinatorics seems novel, and the main results are useful for theoretical understanding of neural networks.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: This paper proves that the reproducing kernel Hilbert spaces of a deep neural tangent kernel and the Laplace kernel have the same set of functions when they restricted to the sphere $S^{d-1}$, which improves the results established in Geifman et al., 2020. Moreover, the paper proves that more non-smooth of the exponential power kernel leads to a larger RKHS with restriction on the sphere $S^{d-1}$ and the entire $R^d$. Furthermore, the authors conduct numerical experiments to verify the asymptotics of the Maclaurin coefficients of the Laplace kernel and NTKs kernel. In summary, the paper is well-written and organized logically. The proof of theoretical results of this paper seems to be correct and reasonable, resulting from the full details of the proof provided in the appendices. 
The contribution of this paper includes two parts. Firstly, it aims to explain why the Laplace kernel and NTK have similar performance in experiments from theoretical point of view by showing that the space of the Laplace kernel and NTK are the same when limited to a sphere. On the other hand, the author reveals the relationship between the smoothness of the exponential power kernel and the corresponding RKHS to explain the better performance of the exponential kernel with a smaller power in the experiments. 
Now I would like to give some comments, 1. Do Laplace kernel and NTK have a similar learning dynamic when we perform kernelized gradient decent in real-world dataset? 2. It is necessary to study the behavior of the NTK and the Laplace kernel outside of $S^{d-1}$. I wonder whether the theoretical results proposed are helpful to improve the performance of Laplace kernel or NTK. 3. The author demonstrates that a non-smooth exponential power kernel leads to a larger RKHS, but whether this indicates that the model obtained by adopting a non-smooth kernel has greater generalization capability. I think the author needs to further theoretically illustrate the relationship between them.

review_title: Review on the theoretical analysis of the relationship between Laplace kernel and NTK

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper uses singularity analysis developed in the context of analytic combinatorics to study the relationship between the reproducing kernel Hilbert spaces of the NTK in a deep fully connected ReLU network, the Laplace kernel, and exponential power kernels. The main results are when these kernels are restricted to the unit sphere. In particular, the authors show that, as vector spaces, the RKHS on the unit sphere of the NTK for a ReLU network of any fixed depth are the same and in fact coincides with that of the Laplace kernel. The authors also compare the RKHS for exponential power kernels, demonstrating that larger powers lead to smaller Hilbert spaces. 

Strong Points: 
1. Understanding the NTK of a deep ReLU networks is a popular and important topic. 
2. The NTK is defined via non-linear recursions, meaning that obtaining quantitative results for deep networks is both technically and conceptually challenging. 
3. Proving that the RKHS of the Laplace and ReLU kernels coincides as vectors spaces is a substantial result.  
4. The authors are the first, to my knowledge, to apply the rather elegant singularity analysis of Flajolet-Sedgewick to study the NTK. Perhaps the closes prior work used free probability to study the spectrum of the NTK. 
5. The paper is clearly written.

Weak Points:
1. As the authors themselves allude to in the discussion, showing that two RKHS are the same as vector spaces ignores the Hilbert spaces structure and can still lead to different inductive biases in kernel regression.
2. The present work applies only to ReLU networks, while the recursive definition of the NTK is valid for rather general non-linearities. 

Overall, this article is a solid theoretical contribution to our understanding of the NTK. In addition to proving concrete results comparing the Laplace, NTK, and exponential power kernels, it is serves as a proof-of-concept for potentially using the tools of singularity analysis to understand neural networks. 
review_title: strong article: RKHS of NTK in deep ReLU nets = Laplace kernel on the unit sphere 

Meta-review: The paper closes an important gap in our understanding of neural tangent kernels. 
In addition, the used techniques are novel. 
My low confidence is mainly based on the fact, that the review process at conference is not perfectly suited to deal with such papers, since their review would actually require both expert reviewers and substantially longer reviewing periods.
Decision: Accept (Poster)