Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper builds and extends the theory of infinite-width neural kernel computations. Compared with prior works, we can summarize its contribution as follows:
(1) It explicitly computes the NNGP and NTK kernels for a wider range of activation functions as shown in table 1.
(2) It derives an explicit expression of the dual kernel for polynomial activation, which also expends the assumption $x, y \in S^{d-1}$ to a more general one $x, y\in R^d$, and suggests using truncated Hermite expansion to approximate the dual kernel for non-polynomial activations.
(3) Given the situation that sometimes we are only given the dual kernel but not the corresponding activation or derivative of the activation functions, this paper propose to compute the dual kernel of the derivative without knowing the activation as shown in theorem 3. 
(4) It uses random sketching techniques to accelerate NTK approximation, which is an extention to previous work which was only applicable for ReLU activation.
strengths_and_weaknesses: Strength:

* This theoretical work extends the previous studies of dual kernels (NTK and NNGP), which is of high quality and might be useful as a good reference for future research in this area.

* Most theorems proved in this paper are incremental, but still preserves enough significance. 


questions: I'm not familar with neural kernels before, so it's hard for me to provide some useful suggestions for this paper.
limitations: The limitations and potential negative social impact are not described since this is a theoretical work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The Neural Tangent Kenrel offers a compelling framework to (partially) understand some theoretical aspects of neural networks, especially near initialization. In the infinite-width regime, It has been known that NTK with ReLU activation has a closed-form analytic formula which enables exact computation of the NTK in this limit. However, the exact kernel computation for general activations is intractable. This paper proposes an approximate kernel computation method that leverages some tools from functional analysis (Hermite decomposition).

strengths_and_weaknesses: **Strengths**:
- The paper is very well written and flows nicely. The problem is well introduced and the results are stated in a logical sequence which serves well the purpose of the paper.
- The theoretical results are sound and 
- The proposed methods are theoretically supported and the numerical results show some superiority compared to traditional methods used for NTK computation.
- The proofs are well structured and easy to follow. I have one question about the proof of Thm3, see Questions section.

**Weaknesses**:
- I believe that it would benefit the paper if approximation rates are provided for general depth L networks instead of just depth 1 networks. The dependency on L would capture the growth of the approximation error as depth increases and maybe suggest when to use (or not use) one method or another. Besides, existing work such as [2] show that NTK tends to deteriorate with depth, I am keen to see what happens to the approximate NTK in this case.
- The paper lacks a more comprehensive literature review. I believe a more in depth discussion of existing results would immensely benefit the paper. See questions section.
- Numerical results are only reported for CIFAR10 (a part the synthetic dataset). It would be better if other (small, not necessarily ImageNet) datasets are included, this would help conclude wether activations such as the exponential or ABRelu is consistently better than ReLU. Also, results for varying depth would add value to the experiments section and make more complete.


questions: - There is a similar NTK decomposition in the “Spherical Harmonics“ basis that appeared in [1] and [3]. Moreover, authors of [2] show a similar extension of the decomposition on S^d to the whole of R^d (Theorem 5 in [2]). Knowing that Spherical harmonics are linked to Legendre polynomials, it would be great if the authors could discuss similarities and differences with Hermite decomposition.
- A recent work ([4]) has showed that NTK computation (in finite-width setting) can be considerably accelerated with some computational tricks. Can the authors comment on the differences (a part from the finite versus infinite width settings of course). For instance, what is the difference between a kernel computed with [4] for width 100 and an equivalent NTK computed with the methods specified in this paper? What can you say about training/inference time?
- In the proof of Thm3, the condition on the second derivative can be further weakened to something like $|\sigma''(t)| \leq C_1 \exp(C_2 t^2 h(t))$ where $\lim_{t \to 0 }h(t) = 0$ and $h$ satisfies some mild conditions.


[1] Geifman et al (2020) “On the Similarity between the Laplace and Neural Tangent Kernels”

[2] Hayou et al. (2021) “Mean-field Behaviour of Neural Tangent Kernel for Deep Neural Networks”

[3] Hayou et al. (2021) “Stable ResNet”

[4] Novak et al. (2021) “Fast Finite Width Neural Tangent Kernel”

[5] Bietti 2021 “APPROXIMATION AND LEARNING WITH DEEP CONVOLUTIONAL MODELS: A KERNEL PERSPECTIVE”
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
In this paper, the authors try to accelerate the computation of NTK with general activation functions. For the q-homogeneous dual kernel,  the authors extend the finite Hermite polynomials approximation technique (Daniely et al. 2016)  and provide approximation bounds. A sketching method is further proposed for the approximation of NTK.   The proposed sketching technique extends the technique (Zandieh et al.  2021) to homogeneous kernels (w.r.t more general activations) with rapidly convergent Taylor expansion. 
strengths_and_weaknesses: 
Pros.
1. This paper focuses on NTK with general activation functions, which is an important direction for understanding deep neural networks with general activation functions. 
2. A method (Theorem 3) is proposed to compute the dual kernel of the derivative of activations without knowing the activations. 
3. The authors provide approximation bound of finite Hermite polynomials approximation to the q-homogeneous dual kernel. 
4. The sketching approximation of NTK extends (Zandieh et al.  2021) to more general homogeneous kernels. 
5. The paper is well organized and well written.



Cons. 
1. An important property of NTK and other prior work with ReLU is the global convergence of training. This relies on the strictly positive definite property in NTK (with ReLU) or positive-definite of the Gram matrix. This may be part of the reason why ReLU is widely used in the assumption of prior work.   This paper focuses on the approximation of NTK with general activation functions; however, it may lose the global convergence property.
2. It seems that the fast sketching approximation technique (Sec.4) can only apply to $K_{\sigma}$ homogeneous dual kernel. The approximation in Eq.(15) is a straightfowrad Gauss-Hermite quadrature for each entry of the kernel $K$, which is brute-force and still with high complexity. There are still some steps needed before claiming to fill the gap for general activations.
3. In Figure 1,  how to compute the time? Is the sketching approximation technique more efficient than orthogonal random features or other fast kernel approximation techniques?
4. It is better to state more clearly the key technique challenging/improvement compared with (Zandieh et al. 2021).  
questions: 1. Does the approximation of NTK with general activation guarantee the global convergence property?

2. How to compute $L$-depth NTK recursively using Eq.(5) ? It is not clearly described in the context.

3. In the experiments,  what is the concrete procedure to compute the time in Figure 1?  It is better to compare with orthogonal random features (Yu et al. 2016) or other fast kernel approximation techniques and present the error vs. number of features besides the error vs. time.


Yu et al. Orthogonal Random Features. NeurIPS  2016. 

Zandieh et al. Scaling Neural Tangent Kernels via Sketching and Random Features. NeurIPS 2021.

Daniely et al. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. NeurIPS 2016.
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The NTK and NNGP are powerful models for understanding and emulating the performance of neural networks in certain conditions. They are also worthy predictors in their own right, and allow one to easily predict with principled uncertainty. These models require computations involving a kernel or covariance function, which is a certain Gaussian integral representing the covariances between activations for two different inputs. Closed form expressions for kernels are known for many activations, each one having been derived by hand in previous works (see table 1). 

The authors introduce a method for approximating NNGP kernels via a polynomial series (Theorem 1, 2). Furthermore, a certain expression in the NTK can be related to the NNGP via a derivative (Theorem 3), so the results readily extend to the NNTK. A random sketching method is also provided to approximate large kernel matrices of deep networks. 

The paper is concluded with some experiments that show that the methods quickly (in terms of both wall-clock and number of series terms) and accurately approximate known NNGPs/NTKs. The authors also observe a 106 x speedup on a toy task compared with the exact kernel evaluation, and show reasonable performance.
strengths_and_weaknesses: Strengths:
- The method is generally applicable, i.e. the conditions in Theorems 1 and 2 are sufficiently mild a wide range of activations of interest. However, I am confused about the condition in Theorem 2 (see question below).
- The authors cite a good amount of relevant literature, which is nice to see. The authors might also be interested in "Stationary Activations for Uncertainty Calibration in Deep Learning", which places the Matern kernel in the context of NNGP kernels.

Weaknesses:
- I did some random sampling of the proofs in the appendix. It is quite possible that I missed some errors. I have some concerns. See "Questions" box.
- I found moving from Definition 1 to equation (5) a bit unnatural. In fact, the original motivation for the NNGP is as either (a) an inner product in an infinitely wide hidden layer with iid zero mean Gaussian weights or (b) the covariance of the output of a network. This is equation (5). Now (5) only depends on a bivariate gaussian (u,v)=(w.x, w.y), hence implying definition 1. Going in this direction is more natural IMO. In contrast, currently the authors go in the other direction and state " By generalizing this observation to vectors in R^d", without any apparent motivation for the generalisation. Note also that it is not actually a generalisation but an iff. A random vector is Gaussian iff all linear combinations are Gaussian. So while it is in principle possible to go from definition 1 to (5) without "generalizing this observation to vectors in R^d", it is not really required to be this abstract. I suggest the authors start with (5) and move to definition 1. That being said, there is nothing technically wrong with the current presentation apart from the word "generalizing".


Typos:
- "NTK can be exactly computed using recursively" removing "using".
- Change "We believe such acceleration thru our methods would open the door to using neural kernels in a wide range of research domains." to "We believe such acceleration through our methods open the door to using neural kernels in a wide range of research domains."


questions: - In Theorem 2, the derivatives need to be absolutely continuous. However, the first derivative of the ReLU is not absolutely continuous (it is not even defined in a classical sense at the origin). So presumably the first half of Theorem 1 does not apply to the ReLU. How then does (12) hold?
- What is the condition required to swap the order of the derivative and the expectation in line 672? Differentiating under the integral is valid when...? The second derivative of the ELU is unbounded, and also does not satisfy your weaker condition (44). Therefore Theorem 3 cannot be applied to the ELU. I don't think this condition is actually required. Differentiation under the integral holds in the sense of generalised functions/distributions/Schwartz functions, as long as the resulting integral is finite. This means that the derivatives will involve Heaviside, Dirac, derivative of Dirac etc.
    - Looking at this again, your Theorem 3 is actually almost identical to part of Theorem 6 of reference [44] that you cite. Their expression for \lambda_3 is your expression for (14), up to a normalisation. Their proof is very similar to yours, but more appropriately uses a Stein's lemma for tempered distributions i.e. Schwartz functions to differentiate under the expectation. I think it is fine to keep your Theorem 3 as is, but acknowledge that this was independently studied in [44] with a much milder condition using Schwartz functions, albeit for a different purpose. Alternatively, cite or reproduce this more general theorem.
limitations: I do not envisage any *direct* societal complications from this work. I hope it is not a cop-out to say that evaluation of societal impact is not necessary for this work, because the contributions are completely task, problem, data and even to some degree model agnostic. Downstream works that use the techniques introduced here should consider these impacts.
review_title: null

Meta-review: metareview: Most prior works on neural kernels have focused on using the ReLU activation. In this work, the authors provide new methods that can approximate multi-layered Neural Network Gaussian Process (NNGP) kernels and Neural Tangent Kernel (NTK) matrices for a wide range of activation functions. All the four reviewers recommended acceptance of the paper.
confidence: Certain
Decision: Accept