Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the relationship between the "pseudo-NTK" and the "empirical NTK". They are different from each other only in the multi-class (multi-output) case: let $f^L_1,f^L_2, \ldots,f^L_O$ denote the $O$ outputs of the network at the last layer $L$. 
If $x_1$ and $x_2$ are two samples,  $eNTK(x_1,x_2)_{i,j}$   

is the inner product between the gradients of $f^L_i$ at $x_1$ and that of $f^L_j$ at $x_2$. On the other hand, the $pNTK(x_1,x_2)$ is a single number equal to the inner product between the gradients of $1/\sqrt{O}\sum_{i=1}^O f^L_i$ at $x_1$ and $x_2$.  It is shown here that the pNTK approximated the diagonal elements of the eNTK, and the off diagonal elements of the eNTK are an order of $1/\sqrt{n}$ smaller (than the diagonal elements), where $n$ is the width of the network. This allows one to construct a faster approximation to the eNTK in the multi-output case. It is also shown that the approximation stays good even if one solves the kernel regression problem associated to the relevant kernels, and many data experiments confirm the findings (though obviously not in terms of exact convergence rates. Some of the experiments show that the approximation holds even after training, though this is not proved from a theoretical standpoint. 

The proof of the main result works by induction (similarly to other NTK papers), iteratively bounding terms in key equation (15), except that one is not taking expectations but instead leveraging the sub-gaussianity of the relevant variables to bound the activations' absolute values with high probability.  
strength_and_weaknesses: Strengths: 
   -This is a very cool topic. I am a little out of touch with the most recent NTK literature but it seems hard to find non-asymptotic results expressed as a function of the width. 
   -There is a good mix of theory and practice and assuming everything is correct, this paper can have an impact both in statistical learning theory and in practical applications. 


Weaknesses: 

  - It is not clearly stated whether or not the main result (Theorem 1, equation (3)) holds only because of the results in this paper or simply because both quantities inside the norm in the numerator converge to the actual (non empirical) NTK at the same rate. I went through the original NTK paper (Jacot et al 18) and it seems like the results are purely asymptotic, but it is still surprising to me that I cannot find a convergence rate (in terms of width) for the eNTK to the NTK. Can the authors provide the relevant references and explain whether their result follows directly from such a non-asymptotic result? 

- The proofs are at best not reader friendly and at worse, wrong: there are three main issues as far as I can see (see more details in "clarity, ...")

1. The management of the high probability events (the "deltas") is very vague. I am quite confident that this can be fixed (possibly by also changing the wording of the main theorems slightly), but since the proofs are not extremely impressive in the first place, it doesn't seem out of place to request a picture perfect first submission for a conference such as ICLR. **Honestly, I think the results are (at least slightly) wrong.** There are a few union bounds arguments missing, which should make a factor of log(L) appear. 

2. The results assume a constant width in the proofs, quickly saying that using other works' would allow one to make the results architecturally robust. It would be nice to see those techniques in action. This is especially relevant in the sense that I think there is a hidden assumption here: I cannot see how to fix the proof of the main theorem without assuming that $O\leq n$ (the number of outputs is less than the width of the network). This definitely restricts the setting and removes some of the typical Xtreme multiclass cases. 

3. The explanations in the proofs are rushed and it can be hard to read some of them. This is despite the fact that the main strategy of the proof is actually pretty straightforward. 
clarity,_quality,_novelty_and_reproducibility: The originality of the work is difficult for me to judge as I am a bit out of practice with this side of the literature, see my question above. 

The clarity needs to be improved (it is not a disaster like many submissions, but there does seem to be some polishing to do). 

Point 1 from weaknesses (details): 

Does \delta_{in} depend on both i and n in Lemma 11?  In the line after equation (21), not only did the authors not define $\delta_g$ (though it is straightforward that it comes from Lemma 18), the delta in the the quantity in the text $(1-\delta)(1-\delta_g)$ cannot be the same as the one showing up in equation (21) itself: in reality there are three sources of failure: the one from lemma 18 ($\delta_g$), the one from the subgaussianity of the first term of equation (20) (let's call this "$\delta_1$") , and the one from the induction hypothesis  (i.e. $\delta_{in}$). The delta in equation (21) should be $\delta_1$, whilst the one in the equation in text should be $\delta_1+\delta_{in}$. There is no way to make this correct even by hiding behind the vagueness of the phrase "where delta depends on delta_in". 

Every layer contains failure events, and the $n_l$'s (the minimum values of n which ensure that the results hold) are defined iteratively. **Every $n_l$ also depends on the  previous delta. **
**There is a union bound over the failure events of each layer missing, which should incur at least a factor of $log(L)$ where $L$ is the depth of the network. In addition, the dependence of the minimum width on the final $\delta$ should be quite complicated (though I agree it is still polylog).**  All of this should be worked out more precisely than it has been done here by throwing everything under the carpet term "high" probability. Note that the minimum required width should also depend on the depth. 


Point 2: 

One of the key calculations in the induction process is arguably inside the proof of Lemma 13, equation (35), where there is a simplification between factors of n, some of which refer to the width of the previous layer whilst some of them refer to that of the next layer. The authors do mention that they are assuming that the widths are within a constant factor of each other, which is indeed necessary for this step to hold. *However, this step needs to hold for the last layer as well, which requires assuming that $O\leq N$, a significant unstated assumption.*



===============Other less key complaints======


There are a few other mid-sized issues with the proofs: 

Lemma 12 is not necessary as we can use Lemma 13 instead (the proofs are nearly identical). 

In the proof of Lemma 11, one uses Lemma 18, which should probably be put before. The quantity $G^{l}$ is from that Lemma but is not properly introduced. Furthermore, between equation (21) and the end of the ensuing paragraph, $G^{l}$ needs to change! This is relevant because this means that after running through the iterations of applying lemmas 11, 12, 13 etc, we should end up with a quantity $G^{l}$ that is quite different from the $G^{l}$ in Lemma 18. 

The proof of Lemma 18 itself is quite problematic. Honestly, I am convinced of the result, but I could only convince myself by looking at the statement and trying to prove it for myself. The proof provided here is very confusing. Certainly the first equality in equation (51) doesn't hold as the variables are not independent. I think this can be fixed with a polarization identity, but that requires a different argument. Note that $\mu$ should also be $\mu^2$ in equation (51). There is also a high probablity statement which is not very thoroughly explained. For instance, when the authors say "with bounded variance", it seems they actually want to refer to the subgaussianity. Just finite variance would not be enough to make the quantities $G^l$ depend logarithmically on $\delta$. Again, the "linear" growth of the quantity bounded in Lemma 18 actually depends on the high probability events considered. One has to mentally assume that all the failure probabilities only end up inside the final estimates in a logarithmic form (which I believe, but is not worked out rigorously). 













summary_of_the_review: This is an interesting paper in a very hot topic. I cannot 100 percent vouch for originality but if the results are indeed original, they are very worthy of consideration. There are correctness issues. Nothing fatal, but the paper needs polishing. 




=======================minor comments, typos=============


Main paper: 

page 4: "casting doubt on the correctness of previous results". This type of provocative statement should be used parsimoniously. I know the authors end up saying that the main contribution of this work is to remove the doubt but still, I would advise reformulating that statement. 


Page 4 " we prefer the sum-of-logits for our networks..." The use of the word "prefer" makes it difficult to see your main point there. The one versus rest analogy probably needs more explanation as well. 

In the experiments (cf. explanation in section 4), the authors seem to say that they provide error bars based on only three samples. Surely this can't be right!

In remark 3, "on diagonal" and "off diagonal" should be swapped. 


Appendix:
At the beginning of section B:   $g:\mathbb{R}^O\rightarrow \mathbb{R}^w$ should be $g:\mathbb{R}^D\rightarrow \mathbb{R}^w$

At the bottom of the same page (13), it would be nice to explain that the vector $1_O$ is not trainable (its gradient doesn't show in the kernel). 

In the second point of "setting" on page 15, there is the condition that the layers should be within a constant ratio of each other. This is not formulated correctly: mathematically, the condition as formulated there is satisfied for any network as long as the widths are integers. 


At the bottom of page 17, there is  $W^{(2)}_{ia}$  

which should be  


$W^{(l+1)}_{ia}$


(line spacing due to formatting difficulties with tex in openreview)


In the proof of Theorem 17 (which is a reformulation of the main theorem of the paper), the proof consists in two cross references, one of which is "??".
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a fast approximation of the empirical neural tangent kernel. The authors theoretically prove the approximation accuracy of the proposed method, and use experiments to demonstrate its performance.
strength_and_weaknesses: Strengths:

Although I did not thoroughly check all the proofs, the proposed methods and the theory look reasonable. 

The experiment results are well presented and look convincing. 

Weaknesses:

The authors mentioned that the motivation for studying the eNTKs is that it provides a good understanding of a given network’s representation. However, by definition, it seems that whenever one can afford to train a neural network, the cost to calculate the eNTK should also be affordable. Therefore the significance of the proposed method is questionable. 

As the authors mentioned, the fact that a eNTK with $NO \times NO$ entries can be approximated by an $N \times N$ kernel matrix is already a well-known result. Therefore the proposed approximation method is not surprising. 

Minor comments:

At the top of page 4, the statement "in the infinite width limit the NTK becomes a diagonal matrix" is inaccurate and may be misleading. If I understand correctly, $K(x_i,x_j)$ for $i \neq j$ is not equal to zero.
clarity,_quality,_novelty_and_reproducibility: Most parts of the paper are written clearly. However, there are certain inaccurate statements that could be improved, as is mentioned in the Strength And Weaknesses section.
summary_of_the_review: The proposed method is reasonable and the theory seems correct. However, the significance and novelty of this paper need further explanation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an approximation of the neural tangent kernel (NTK) for models with a large output dimension. Specifically, considering a model with output dimension $O$, for a specific pair of data examples, the standard definition of NTK gives an $O\times O$ matrix. This paper tries to approximate the standard NTK by the identity matrix multiplied with a scalar which is defined as the average of the original NTK. It is proved that as the width goes to infinity, the approximated NTK converges to the standard NTK in Frobenius norm and spectral norm, and the kernel regression solutions are also close. The theoretical results are further supported by experiments.
strength_and_weaknesses: I think this is an interesting work for NTK approximation, and indeed the proposed method can save the memory usage by a factor of $O^2$. However, I am not very sure about novelty, as detailed below. 
1. As mentioned on top of page 4 of this paper, some recent work already points out that the standard NTK converges to a diagonal matrix as width goes to infinity. This paper further provides formal theorems (Theorems 1, 4 and 5), but the technical challenge and innovation are not discussed. For example, for convergence in Frobenius norm, I imagine it just follows from randomness of the last layer, and we do not need to deal with some independence issue since other matrices and vectors involved in the gradient calculation do not depend on the last layer, which can simplify the proof a lot. Please correct me if I am wrong, but either way I think it is necessary to discuss the technical difficulties to justify innovation.
2. An interesting result is shown in Figure 7, where the kernel regression outputs of the standard NTK and approximated NTK actually become closer during training. I believe this is a novel discovery, but there is not enough discussion.
clarity,_quality,_novelty_and_reproducibility: I feel the paper writing can be further polished: for example, Figure 2 and 3 appear on page 3, but are referred to on page 5. I think the figures can be rearranged. 
summary_of_the_review: This paper proposes an efficient way for NTK approximation and provides interesting results, but more justification of novelty is needed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In the paper, the author provided some theoretical and experimental results on the so-called "sum of logits" approximation of empirical neural tangent kernel (eNTK) having multiple output units.
The proposed approach consists in approximating the eNTK by a block diagonal matrix as the Kronecker product between some pseudo-NTK approach (pNTK) and $I_O$, the identity matrix of size $O$, if the network has $O$ output units. This saves an order $O^2$ of memory and (up to) order $O^3$ of computation in the evaluation of NTK.
The authors showed, in Theorem 1 and 4, respectively, that the relative difference in Frobenius norm and maximum eigenvalue between the proposed approximation and the true eNTK is of order $O(n^{-1/2})$, for deep networks of width $n$ and with Gaussian random weights. This provides theoretical justifications for the proposed approximation.
Further numerical experiments were provided to validate the proposed approach at and beyond initialization.
strength_and_weaknesses: **Strengths**: the paper is in general well written and easy to follow (a few clarifications are needed, though, see my detailed comments below in "Summary Of The Review." The obtained theoretical results are of interest, believed to be true in the literature, but, to the best of my knowledge, rigorously established for the first time. I did not check the proof in great detail, but the line of arguments looks compelling.

**Weaknesses**: the theoretical results obtained in the paper are not very strong and are limited in many aspects (layer width, Gaussian initialization, nonlinearity, etc). Some improvements can be obtained without much effort, see again my detailed comments below.
clarity,_quality,_novelty_and_reproducibility: **Clarity**: the paper is in general well written and easy to follow (a few clarifications are needed, see my detailed comments below in "Summary Of The Review." 

**Quality and Novelty**: the contributions in the paper are of interest and somewhat novel (theoretical and empirical evaluations of some existing ideas).

**Reproducibility**: The proof is fine. The authors claimed "we plan to share computed pNTKs for all the mentioned architectures ...", which is, however, not present in the current version of the paper.
summary_of_the_review: I find the contributions of the paper marginally significant or novel. And some clarifications and revisions are needed to help better understand and possibly (re)evaluate the contribution of this work. See below.

Detailed comments:
* P1: I imagine NNGP stands for neural network Gaussian process?
* i'th at the bottom of P3 versus ith in P4
* P4: I get confused when reading "Before turning to the formal results and experimental evaluation, we give some intuition. First, suppose that ...": I suppose that here v_i should be the ith row or column, NOT entry, of a linear read-out layer? Since in the sentence that follows "if the vectors v_i \sim \mathcal N(0, \sigma^2 I_O)"
* Theorem 1: can something be said beyond the current setting? Say, beyond ReLU activation? Different initialization scheme, say, beyond Gaussian? Should we understand \in O(n^{-1/2}) as of order O(n^{-1/2}) as in classical computer science or statistic literature?
* Remark 3 and Figure 2: the referred "ratio of information" here should be explicitly defined and (at least briefly) discussed
* I believe it is necessary to mention in the statement of Theorem 1 that the result holds ONLY for networks having random weights or networks at initialization: in the current version of the theorem this fact is somehow very implicit and this makes a huge difference.
* Theorem 4 and its proof: in fact, the result (and proof) in Theorem 4 can be improved to obtain some control on any corresponding pair of eigenvalues of eNTK and its approximation: it in fact follows from  Weyl's inequality (in linear algebra) that max_{i} |\lambda_i (A) - \lambda_i (B)| \leq \| A - B \|, with \lambda_i(A) eigenvalues of A and \| A \| the spectral/operator norm of A. Some conclusions on the condition number can be drawn in a similar manner.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces pseudo-NTK (pseudo-Neural Tangent Kernel), a provably efficient technique to estimate empirical NTK. The authors in particular show that the relative difference in Frobenius norm and maximum eigenvalue between the proposed approximation and the true empirical NTK is of order  $O(n^{−1/2})$ for deep networks of width n. Empirical results are provided that show the practicality of the results.

+ the paper looks at a deep learning model that is compatible with i) a connection with kernel methods and ii) is amenable to a theoretical analysis; it gives well-grounded insights on deep learning models;
+ the authors prove computational gains wrt to existing eNTK;
+ there are empirical results that are provided to test the efficacy of the method;

- if, as stated by the authors, the paper should be "looked at whole", the amount of revisions and changes done by the authors since the first submission plays a role; here, this amount is pretty big, containing correction of unclear statements, refactoring of some proof, new explanations; the paper is significantly different (and better) than the submitted version.
justification_for_why_not_higher_score: The amount of revisions since the first submission is too large for if the paper were to have higher score (already bumped by one reviewer) to remain fair compared with other papers.
justification_for_why_not_lower_score: Interesting topic, with contributions from the statistical and algorithmic field.
Decision: Reject