Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives an approximation method for calculating neural tangent kernel with random features and sketching. The algorithm significantly speeds up the original NTK computation.
main_review: The method described in the paper address the vital running time problem of the original NTK. The experiments verify the speed up by a large factor. The time complexity is well studied in the paper.

I have some concerns in the writing, as it seldomly introduces the original NTK and then directly in the proposed algorithm itself, which is unfriendly to some readers. 
limitations_and_societal_impact: 
There are many complexity notions in the paper that are hard to digest, e.g. in the feature dimension sample complexity in 192, is there a dominating factor within the \Omega notion, as it later needs to compare with previous works?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this manuscript the authors propose and analyze a sketching scheme that allows for more efficient computations involving so-called neural tangent kernels and their convolutional counterparts. By leveraging recent work on sketching tensors and polynomial kernels from [1] the authors provide algorithms for depth L networks with provable guarantees on the quality of the feature embedding (provided the sketch size is large enough). To complement these theoretical developments the authors provide spectral approximation bounds for a variant of their method in a simplified setting (L = 1). Lastly, some numerical results are provided to illustrate the potential efficacy of the method in practice.
main_review: Overall, this manuscript has nice results, though as written it feels like the big step/insight was in ref. [1] where the sketches are constructed. The main contribution here is then showing/observing the requisite structure is present in the (C)NTK. As the structure of the NTK is from prior work (e.g., refs. [9] and [12]) it does feel like some of the more substantial contributions relate to observations about the CNTK, (limited) spectral approximation bounds, and showing a level of numerical feasibility. I do think there are some improvements that could be made to the manuscript to better explain aspects of these contributions

In section 4 the authors note that there are specific structural observations they make about the CNTK that allow it to be efficiently sketched. Do those observations alone yield a faster algorithm than what is cited from [5]? Additionally, while the dependence on $d_1$ and $d_2$ is better than [5] the cost is worse in L and an epsilon is introduced. Thinking of the image sized as fixed (which seems reasonable in certain settings), this means there is a network depth (or desired accuracy) at which point the exact computation is seemingly preferable; is that the case? and how should that trade-off be evaluated?

In the numerical results the authors have to pick parameters (beyond just the final feature size), how are these chosen? Moreover, even the final feature size does not necessary seem to be directly guided by the theoretical results (i.e., the theory suggests larger sketch sizes may be warranted) the paper shows the sketch sizes chosen yield decent results. Is there some "practical guidance" that could be applied here? How were other internal parameters (e.g., in Alg. 1) chosen?

In some of the algorithms there are two distinct steps: (1) approximation by a polynomial kernel and (2) a specially designed sketch for that kernel. While the polynomial kernel order is chosen adaptability, is that "convergence" with epsilon balanced with the sketch convergence? Roughly speaking, as \epsilon -> 0 would the method, at some point, be reasonably thought of as using an "exact" polynomial kernel? and, if so, what are the implications of that? Some of the properties of the NTK cited by the authors (e.g., generalization) depend on kernel properties such as minimal eigenvalues. The behavior of some of those properties could look quite different for a smooth polynomial kernel vs the less smooth zonal kernel induced by ReLU. This presumably relates to the authors informal discussion of regularization effects.

While I think it is reasonable that this paper sets itself in the "NTK regime" and is presented as a computational improvement for that setting, it may be reasonable for the paper to briefly note that the NTK regime is not fully descriptive. See, e.g., When Do Neural Networks Outperform Kernel Methods? by Ghorbani et al. NeurIPS 2020 and references therein.

Assorted comments/suggestions/questions:

- In places the authors rely a bit too much on "inheriting" information from ref. [5]. For example, Theorem 4 explicitly calls out a model defined in [5] as do some of the CNTK numerical experiments. These details seem important enough that they warrant inclusion somewhere in this work (e.g., the supplement) so that the reader can actually see what the models are.

- Early in the intro $x_i$ is introduced as a $d \times d$ image and then later is generically a d dimensional vector. I think it would be better to keep x as a d-dimensional vector and reserve some other letters for matrix/tensor representations of images to avoid potential confusion (similarly, maybe it is better if images are always $d_1 \times d_2$ to avoid overloading d).

- Should eq. (12) have the inequality flipped or a $1-\delta$ on the right hand side?

- On line 136 the abbreviation DP used later for dynamic program should be properly "defined."

- The manuscript could be a bit more clear about what all operations are explicitly included in the timing reported. There is a brief note on this in 5.3, but what about for the CNTK?

- The manuscript may benefit from having a bit more notation introduced earlier on. This would make it easier to talk concretely about kernel learning, features maps, etc. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 

In this paper, the authors propose a method to approximate NTK by sketching the polynomial expansions of arc-cosine kernels. The POLYSKETCH  sketch technique is used to reduce the dimensionality of high-degree tensor products.  Moreover,  the approximation error is theoretically analyzed.
main_review: 

Pros.
1. Approximate ReLU-NTK by truncation of Taylor series of expansion of arc-cosine kernels is interesting.  The corresponding approximation error bound is new. The complexity of the feature dimension is smaller than the gradient-based approximation scheme (Arora et al, 2019). 
2. The paper is well organized and clearly written.

Cons. 
1. Although I appreciate the theoretical contribution, the motivation of acceleration ReLU-NTK is unconvinced for me.  Theoretical analysis gradient-based approximation is for better understand deep neural network training. In contrast, this paper focus on the acceleration of learning with ReLU-NTK.  However, even exact ReLU-NTK works not well compared with deep neural networks.  The proposed acceleration may not be easy to find practical applications. 

2. The paper focuses on ReLU-NTK approximation and acceleration. However, the empirical test focuses on the downstream classification and regression.  It is better to show the empirical study of the approximation error compared with different baselines. 
limitations_and_societal_impact: The limitations are clearly stated.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work combines dot product kernel approximation via Taylor series and arc-cosine kernel approximation for NTK approximation for deep ReLU neural networks. In particular, to avoid the exponential increase in $L$, POLYSKETCH is applied to guarantee the complexity to be linear in the depth $L$. Besides, the leverage sampling based strategy is also developed for arc-cosine kernels and further for NTK. 
main_review: I happen to review this paper again. This submission merged two papers and addressed most of my previous concerns. Therefore, I have no further comments on this paper except the following minor issues:


1.	In the experiments, the MSE metric should be changed to $|| K - \tilde{K} ||/|| K ||$ in some norms for intuitive/fair comparison. Please follow experimental settings of previous works on random features/Nystrom approximation.

2.	The obtained approximation bound in Theorem 1 might be loose due to two independent constants $\epsilon$ and $\delta$. It would be possible to obtain a tight bound? E.g., an exponential order decay following the fashion of concentration inequalities. I don’t check the proof carefully but I think the JL transform used in the proof of Theorem 1 could be improved?

3.	One paper on leverage score based sampling for random features is missing:

*Li, Z., Ton, J. F., Oglic, D., & Sejdinovic, D. Towards a unified analysis of random Fourier features. ICML2019.*

The used technical tools for spectral approximation is also based on the matrix concentration inequality, see Lemma 4 for details. This paper and other random features literature [37] require the random feature map to be continuous, which in fact excludes the zero-order arc-cosine kernel (corresponds to the step function). How to address this when applied to NTK?

4.	The expression “low-dimensional feature maps” is inaccurate. The dimension of the obtained feature map is larger than d but is smaller than n. So it would be better to polish this.

5.	The Gibbs sampling used in Algorithm 3 seeks for an approximation sampling as the modified distribution q(w) is intractable to be sampled.


6.	Some reference information should be checked, e.g., [36] published on NeurIPS2007 and [37] published on NeurIPS2017. 

limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper considers sketching and random feature methods to accelerate learning with the Neural Tangent Kernel (NTK). NTK based methods are promising linearized approximations of non-convex neural network models, however, they suffer from the high computational complexity of kernel matrix operations. Scaling NTK methods via randomized approximations is a promising direction towards understanding deep neural networks and matching their performance using simpler architectures such as linear kernel machines. 

The reviews all agreed that the paper contains interesting theoretical and experimental results, and expressed minor concerns and suggestions.  One reviewer pointed out that a discussion of the regime in which NTK is not fully descriptive would be useful. Another reviewer commented that the complexity notions are hard to digest. Overall, the paper received generally positive reviews, while some of them pointed out certain minor problems and gave above borderline scores, they all recommended accepting the paper. Please take into account the updated reviews when preparing the final version to accommodate the requested changes.
Decision: Accept (Poster)