Divergence of Neural Tangent Kernel in Classification Problems

There may be some misunderstandings between us, and we would like to take this opportunity to address them one by one.

---

1. ”The main contributions of this paper are trivial since the derivation in Eqs. (2.7)-(3.2) is common-used.“

These equations are not our core results but are used to set up the problem. They are standard in NTK theory. Our theoretical contribution lies in Theorem 2.

In our paper, the content of Eqs. (2.7)-(3.2) is as follows:

Equation (2.7):

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{~d} t} \theta_{t} & =-\nabla_{\theta} \mathcal{L}\left(\theta_{t}\right)=-\sum_{i=1}^{n} \ell^{\prime}\left(\left(2 y_{i}-1\right) f\left(x_{i} ; \theta_{t}\right)\right)\left(2 y_{i}-1\right) \nabla_{\theta} f\left(x_{i} ; \theta_{t}\right) =\sum_{i=1}^{n} \nabla_{\theta} f\left(x_{i} ; \theta_{t}\right)\left(2 y_{i}-1\right) u_{i} . \end{aligned}$$

Equation (3.1):

$$K_{t}\left(x, x^{\prime}\right)=\left\langle\nabla_{\theta} f\left(x ; \theta_{t}\right), \nabla_{\theta} f\left(x^{\prime} ; \theta_{t}\right)\right\rangle .$$

Equation (3.2):

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{~d} t} f\left(x ; \theta_{t}\right) =\left[\nabla_{\theta} f\left(x ; \theta_{t}\right)\right]^{T}\left[\frac{\partial \theta_{t}}{\partial t}\right] =\sum_{i=1}^{n}\left[\nabla_{\theta} f\left(x ; \theta_{t}\right)\right]^{T}\left[\nabla_{\theta} f\left(x_{i} ; \theta_{t}\right)\right]\left(2 y_{i}-1\right) u_{i} =\sum_{i=1}^{n} K_{t}\left(x, x_{i}\right)\left(2 y_{i}-1\right) u_{i} . \end{aligned}$$

These three equations are not our core results but are used to set up the problem. They are standard in NTK theory. Specifically:

1. Equation (2.7) describes the dynamics of neural network parameters under gradient descent.
2. Equation (3.1) provides the standard definition of the (empirical) Neural Tangent Kernel (NTK).
3. Equation (3.2) describes the dynamics of the neural network function during gradient descent.

Our theoretical contribution lies in Theorem 2, which demonstrates the divergence property of the NTK. In Theorem 2, we state that as the training time $t \to \infty$ , the empirical NTK $K_t(x, x{\prime})$ may not converges, which offers a perspective that differs from the conventional assumption of NTK convergence in regression tasks. We greatly value your feedback and hope this clarification helps address your concerns.

---

2. ” Besides, the finding that the empirical NTK does not consistently converge but instead diverges as time approaches infinity has been observed by existing studies.“

In fact, to the best of our knowledge, we have not seen studies addressing the divergence of the NTK in previous literature, especially in classification problem. For regression problems under the Mean Squared Error (MSE) loss, it is commonly believed that the NTK converges [Allen-Zhu et al., 2019; Xu and Zhu, 2024].  If you are aware of works that explore the divergence of the NTK, we would be sincerely grateful if you could share them with us. Thank you for your valuable insights.

---

References

[Allen-Zhu et al., 2019] Allen-Zhu, Z., Li, Y., and Song, Z. (2019). "A convergence theory for deep learning via over-parameterization." In International Conference on Machine Learning, pages 242–252. PMLR.
[Xu and Zhu, 2024] Xu, J., and Zhu, H. (2024). "Overparametrized Multi-layer Neural Networks: Uniform Concentration of Neural Tangent Kernel and Convergence of Stochastic Gradient Descent." Journal of Machine Learning Research, 25(94), 1–83.

Thank you for your review. We will now attempt to address your questions.

In Theorem 1, it is assumed that the minimum eigenvalue of the NNK matrix has a lower bound. However, the eigenvalues of the NNK Gram matrix approach zero as the number of training examples increases, as demonstrated in the two papers below. Can this observation offer any insights into NTK theory for classification problems?

Thank you for pointing out that the eigenvalues of the positive definite NTK indeed decay to zero, and there is no constant lower bound greater than zero. Also, the lower bound $\widetilde{\lambda}_0$ of the eigenvalues of the NNK Gram matrix will also face a similar issue as $n \to \infty$. Regarding this problem, in fact, our "divergence" conclusion was indeed for a fixed $n$, not in the asymptotic sense of $n$. Our conclusion is: For each training with sample size $n$, the NNK diverges during this training process.

To see the significance of this result, we can compare it with regression problems: In regression, regardless of the value of $n$, as long as $m$ is sufficiently large, we can achieve uniform convergence of NNK to NTK, then approximate neural networks using kernel regression, and thus obtain properties of generalization ability [Lai et al., 2023; Li et al., 2024a]. However, in classification problems, NNK cannot uniformly converge to NTK. Although when $n$ is sufficiently large, the lower bound of the gap between NNK and NTK, $\frac{\lambda_0}{2n^2}$, is small, this small lower bound still makes it difficult for us to approximate neural networks using kernel regression.

In summary, what we want to express is "divergence" in a single training, not divergence in the asymptotic sense as $n$ grows. Therefore, although $\frac{\lambda_0}{2n^2}$ is very small, this issue does not affect the main conclusion we want to express. However, we have to admit that it doesn't look that elegant—we just haven't thought of how to weaken this condition yet.

Could the scope be broadened to incorporate other classification loss functions in order to gain a more comprehensive understanding of NTK behavior?

Yes, our conclusions can indeed be extended to more general loss functions. In fact, the influence of the loss function is reflected in equation (C.22) of our proof. Let the loss function be $l(x)$, which appears in training as $l((2y_i - 1) f(x_i))$. It can be easily verified that if the loss function satisfies: 1) convexity; 2) $l'(x) < 0$, then the proof of equation (C.22) still holds. We only need to let $u \coloneqq \frac{\partial l((2y_i -1) f(x_i))}{\partial f(x_i)}$, and let $V(u(\cdot)) = l(\cdot)$. In the previous version of our paper, we only selected the representative cross-entropy loss function. Thank you for your suggestion; we will add more explanations in the paper to show that our proof is general.

What will happen if the data is completely separable or follows a Gaussian mixture in classification problems?

Thank you for your suggestion. While we find the question raised by the reviewer interesting, it deviates from the scope of our current work, which does not make assumptions about the data distribution. Developing a comprehensive framework that incorporates such assumptions to weaken previous assumptions (like the positive definiteness of the NTK) and utilizes techniques related to separability [D. Soudry, et al.; H. Taheri and C. Thrampoulidis] is beyond the scope of this paper. We thank you for highlighting this possibility and hope that our study will inspire further research in this direction.

[D. Soudry, et al.] The Implicit Bias of Gradient Descent on Separable Data. ICLR 2018.

[H. Taheri and C. Thrampoulidis] Generalization and Stability of Interpolating Neural Networks with Minimal Width. JMLR 2024.

[Lai et al., 2023] Lai, J., Xu, M., Chen, R., & Lin, Q. (2023). Generalization ability of wide neural networks on . arXiv preprint arXiv:2302.05933.

[Li et al., 2024a] Li, Y., Yu, Z., Chen, G., & Lin, Q. (2024). On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains. Journal of Machine Learning Research, 25(82), 1–47.

Thank you for your additional comments. We will now compare our results with the articles you mentioned.

The Relationship Between Existing Overfitting Results and This Paper

"The divergence result of the NNK is not particularly surprising, as it is evident that parameters and outputs must diverge to minimize standard classification losses such as logistic, softmax, or exponential losses."

Our main difference from this kind of overfitting is that in our setting, we fix $m$ and let $T$ approach infinity. In [Z. Ji and M. Telgarsky] and [H. Taheri and C. Thrampoulidis], the setting is to consider a certain time $T$ and then let $m$ become large enough. In the latter case, we can imagine that $f(x)$ tending to infinity does not directly indicate the divergence of the empirical NTK because $m$ is also changing accordingly.

In fact, this is precisely a subtle difference. To illustrate the distinction between the two more specifically, please allow me to ignore technical details and make a brief argument here:

Assumption: For simplicity, we use the assumption that the NTK is positive definite, although, as you said, this is a too strong assumption.

Fix a certain time $T_{\max} \in [0, \infty)$, we can prove that within the time interval $[0, T_{\max}]$, with high probability, the NTK regime holds: $\parallel W_{t} - W_{0}\parallel_2 \leq O(\sqrt{m})$. Since $T_{\max}$ is finite, we can control the sum of gradients in $[0, T_{\max}]$. Furthermore, we can prove that when $m \to \infty$, the empirical NTK converges uniformly in $[0, T_{\max}]$. Then, as long as we take $T_{\max}$ large enough and combine it with the positive definiteness of the NTK, we can prove that the loss of the neural network becomes arbitrarily small.

It can be seen that the "uniform convergence of NTK" in the above process is different from the "divergence of NTK" in our paper, precisely because of whether we fix $m$ or fix $T$.

So why does our setting fix $m$ first, or in other words, what is the purpose of our paper? As is well known, the fact that the loss of neural networks approaches zero is not the end—people are also concerned about the specific generalization ability of overfitted neural networks, especially what happens during the process of $T \to \infty$ after the neural network has overfitted (e.g., whether so-called benign overfitting occurs). To achieve this, in regression tasks, based on the overfitting of neural networks [Du et al., 2019], people have proved that sufficiently wide neural networks converge uniformly to the corresponding kernel predictor at any time $T \in [0, \infty)$ [Lai et al., 2023; Li et al., 2024a]. Then, they study the properties of the corresponding kernel predictor, thus completely characterizing the generalization ability of over-parameterized neural networks [Li et al., 2024b].

However, in classification tasks, our work aims to show that although networks can still overfit, this is due to a not entirely identical mechanism because over-parameterized neural networks will no longer converge uniformly to the kernel predictor. Therefore, during the process of $T \to \infty$, what happens to the neural network may be difficult to analyze from the perspective of NTK. We propose this perspective to inspire future work.

Thank you very much for the literature references you provided! ! We will compare the above literature in our article and briefly describe the above argument process. This is indeed a subtle but meaningful comparison. Moreover, during the process of writing the rebuttal, we also realized that the theoretical significance in our article is not fully explained; we actually need the above comparison to completely characterize our work. Thank you again for your review comments, which greatly supplement our work.

Here is part of the new paragraph of the literature comparison that we plan to include in the paper, while the discussion of theoretical significance will be included in another section:

Recent works, such as [Z. Ji and M. Telgarsky] and [H. Taheri and C. Thrampoulidis], have explored the dynamics of overfitting in neural networks under the regime where the network width $m \to \infty$ and the training time $T$ is fixed and finite. These studies demonstrate that under such conditions, the network will overfit under weaker conditions on NTK. In contrast, our work examines the case where $m$ is fixed and $T \to \infty$. We show that in this setting, the NTK exhibits divergence, preventing uniform convergence to kernel predictors and revealing distinct overfitting dynamics in classification tasks.

Thank you for the detailed response. The paper will be well-positioned in the literature by emphasizing the differences from related works, as the authors responded.

The fact that the loss of neural networks approaches zero is not the end—people are also concerned about the specific generalization ability of overfitted neural networks

I would note that the work I mentioned in my review comments also proved the generalization of overparameterized models for classification. These results use NTK but do not require the fixed NNK argument. This is why I thought that showing the divergence of NNK is not critical.

While the divergence of NNK for classification is intuitively expected, proving it rigorously is indeed important. I have increased my score to 6 in the expectation that the aforementioned points will be also acknowledged in the revised version.

Thank you very much for your careful review and recognition of our work. Below, we respond to some of the questions.

"While I don't question the novelty of the result in literature, I don't necessarily find it too surprising. To truly minimize the cross-entropy would require $f(x_i,\theta)\to +\infty$ for $y_i=+1$ (and similarly for the other class)."

Indeed, some previous works [Z. Ji et al. 2020; H. Taheri et al. 2024] have already proven that for fully connected neural networks under the cross-entropy loss, the loss function approaches zero, which implies that $| f(x_i,\theta)|\to \infty$. However, there is a subtle but important difference between our work and these existing studies. Let me briefly explain, ignoring technical details.

In existing works, the general idea is to first fix a large training duration $T_{\max}$, and then provide a threshold for network width m_{T_\max}. Then, letting $T_{\max} \to \infty$ with m \geq m_{T_\max}, it can be proven that finally $| f(x_i,\theta)| \to \infty$. However, this kind of overfitting cannot explain the divergence of NNK. In fact, we can even prove that under this setting, the NTK remains convergent: Fix a certain time $T_{\max} \in [0, \infty)$, we can prove that within the time interval $[0, T_{\max}]$, with high probability, the NTK regime holds: $\parallel W_t-W_0\parallel_2\leq O(\sqrt{m})$. Since $T_{\max}$ is finite, we can control the sum of gradients in $[0, T_{\max}]$. In this way, we can prove that when $m \to \infty$, the NNK converges uniformly to NTK in $[0, T_{\max}]$. Moreover, based on this, if the NTK is positive definite, then letting $T_{\max} \to \infty$, we can prove that $| f(x_i,\theta)| \to \infty$. In summary, under this setting, the proof of overfitting cannot explain the divergence of NNK, because $m$ also changes with time $T_{\max}$.

Unlike existing works, we aim to conduct a consistent analysis of a neural network, rather than just exploring whether it can overfit. After all, besides overfitting, people are also concerned about the "shape" and generalization property of network after overfitting (e.g., whether benign overfitting occurs). Therefore, we choose to fix $m$ first, and then let the training time $T$ tend to infinity. This is natural and reasonable for neural networks. Under such a setting, in regression problems, uniform convergence can occur, allowing people to use kernel regression to study the generalization ability of neural networks [Lai et al., 2023; Li et al., 2024a; Li et al., 2024b]. However, in classification problems, according to our results, kernel regression approximation is not possible. That is, the overfitting of neural networks in regression and classification problems is actually due to different reasons. This is the theoretical significance revealed by our setting.

This difference in setting makes the analysis of neural network properties more challenging—after all, we cannot directly use the NTK approximation. This is why we devised a rather clever proof by contradiction to prove our conclusion, rather than following existing methods to obtain $|f(x_i,\theta)|\to\infty$, and then directly carry out subsequent proofs based on $|f(x_i,\theta)|\to\infty$.

We indeed overlooked the comparison with existing results in the article, which caused our contributions not to be highlighted. Thank you for your question and suggestion, and we hope this response can alleviate your doubts.

Minor points

"line 163: you don't optimize the parameters with gradient flow. Gradient flow is used to (approximately) analyze the optimization process."

1. Thank you for your reminder. We indeed did not emphasize this point as you pointed out. In practice, training uses gradient descent, and gradient flow is just an approximation when the step size tends to zero. This approximation has an impact; in fact, many works consider gradient descent and make assumption on the step size (e.g., [Du et al. 2018]). We will use more rigorous expressions here.

"line 185: this is badly written. You already defined $K_t$ in (3.1) - why are you repeating it in (3.3) as though it was new?"

2. We apologize for this typo. Equations (3.1) and (3.3) have the same content. We will delete (3.3), keep only (3.1), and reorganize this paragraph. We did not notice this problem before; thank you for careful reviewing!

"line 283: '...will converges to NTK with probability as width comes to infinity...' Do you mean 'will converge with probability 1' or 'will converge in probability'?"

3. What we intended to express is indeed "converges in probability". This is indeed a writing typo and thanks for pointing it out.

"Theorem 2: (4.4) is precisely equivalent to (4.3). Are these meant to refer to different networks (i.e., should (4.4) be modified to refer to ResNet)?"

4. Yes, the second part of the theorem is about $K^{\mathrm{Res}}$; this is also our typo. Thank you very much for pointing it out.