Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension

Bounds on the smallest eigenvalue of the neural tangent kernel (NTK) are a key ingredient in the analysis of neural network optimization and memorization. However, existing results require distributional assumptions on the data and are limited to a high-dimensional setting, where the input dimension $d_0$ scales at least logarithmically in the number of samples $n$. In this work we remove both of these requirements and instead provide bounds in terms of a measure of the collinearity of the data: notably these bounds hold with high probability even when $d_0$ is held constant versus $n$. We prove our results through a novel application of the hemisphere transform.

Paper

References (48)

Scroll for more · 36 remaining

Similar papers

Peer review

Reviewer Hffy7/10 · confidence 3/52024-07-02

Summary

This paper gives a lower bound of the smallest eigenvalue of the NTK matrix for shallow and deep connected ReLU networks through the application of hemisphere transform.

Strengths

The main significance of this paper is dropping the requirement of the input data dimension from [Nguyen2021] on the same topic, enabling more flexible application in other machine learning problems. The main result is presented with a clear step-by-step proof sketch. Reference: - *Quynh Nguyen, MarcoMondelli, and GuidoMontúfar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8119–8129. PMLR, 18–24 Jul 2021.*

Weaknesses

I do not see any major weakness of this paper. It could be nicer if this paper also offers experimental results to support their calm.

Questions

How tight is the lower bound shown in Theorem 1 where the quantity $\lambda$ is defined in terms of the $\delta$-seperated-ness of the data, besides the case where data distributed uniformly on the sphere mentioned in line 152-153?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

This paper is theoretical and limitations are stated clearly in the paragraphs (lines 317-320).

Reviewer qjpA6/10 · confidence 5/52024-07-09

Summary

This theory paper fits within a general framework in which one tries to get information on training of deep learning models using the formalism of the so-called Neural Tangent Kernel. Specifically, the topic is smallest eigenvalue control for the NTK kernel, and the authors study the minimum eigenvalue under the assumption that one has datasets of unit norm and assume that the data are "well spread" i.e. they have controlled separation constants (and sometimes controlled covering, meaning the data are "uniformly spread"). The obtained bounds depend on this separation constant and on the input and output space dimensions. The technique uses the so-called hemisphere transform and basic harmonic analysis on the sphere. These methods have not been used before for this particular problem.

Strengths

The studied problem is arguably relevant for dynamical study of NN evolution. The techniques used are innovative within this field.

Weaknesses

The main weakness is that requirement on the data distribution to be delta-separated is not as "harmless" or "general" as the authors claim (furthermore, I did not find a justification of this claim in the paper; the authors just state that $\delta$-separation is "milder" than previous work requirements, without explaining why and without verifying that). In practice, it is not trivial to ensure that a sample from a data distribution is well separated in the sense of theorem 8, or a Delone set with controlled constants, making it uniformly separated in the sense of Theorem 1. The assumption of iid data is in practice easier to justify, and checking for delta-separation may be itself a hard problem.

Questions

Main question: A step for a good comparison to previous work is in having formulated Corollary 2, that is an "iid data analogue" of the main result of thm 1. However it is not clear how the bounds from previous works compare to this result. I suggest to put some effort to explicit this comparison in the most explicit way possible. Other minor observations and questions: 1) the notion of "$\delta$-separatedness" is a terminology used in the community for the case that points are at minimum distance larger or equal than $\delta$. The notion is not the same as used in this paper, and defined in line 44. Also, at 3 instances in the paper the notion of "collinearity" is used, which is a bit misleading: any two points are collinear. So I suggest to replace "collinearity" with something more explicit such as "being on the same line through the origin" and that the notion of "$\delta$-separated" is either called by a different name, or that it be emphasized the difference with the usual notion. 2) In the paragraph before line 39, there is an instance in which $\mathbb R^{d\times n}$ should be replaced by $\mathbb R^{d_0\times n}$. 3) Section 2 has a large overlap with the introduction. Could it be shortened or merged? 4) lines 141-142, about data in $\mathbb S^1$: this sentence is not clear to me, and it is not clear how passing from $\mathbb S^1\subset \mathbb R^2$ to $\mathbb S^1\times\{0\}\subset \mathbb R^3$ affects the constant $\delta'$ from Theorem 1. 5) line 243-244 and lines 313-315: the fact that data are required to be $\delta$-separated has to be mentioned, since it restricts generality.

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

The main concerns were mentioned in the "weaknesses" part.

Reviewer k95g6/10 · confidence 3/52024-07-10

Summary

This work provides bounds on the smallest eigenvalue of the Neural Tangent Kernel corresponding to fully connected ReLU networks trained on data supported on spheres. The novelty is that usual assumptions coupling the input data dimension to the sample size are able to be weakened. Similarly, assumptions on the data distribution are replaced by a condition on its realization, that the datapoints are $\delta$-separated.

Strengths

This paper is well written and provides a novel result that gives valuable insight into the behaviour of the NTK.

Weaknesses

The major weaknesses of the paper are addressed by the authors and provide avenue for future research.

Questions

None

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have addressed the limitations of the work. This is a theoretical paper so the broader societal impact is negligible.

Reviewer fqQK6/10 · confidence 5/52024-07-11

Summary

This paper investigates the neural network optimization and memorization in terms of the bounds on the smallest eigenvalue of NTK, without requiring distributional assumptions on the data. The theoretical results are technically sound and contribute to the understanding of neural network convergence behavior.

Strengths

1. The bounds hold without requiring the distributional assumptions on the data and being applicable to high-dimensional settings. 2. The authors introduce a novel application of the hemisphere transform and the addition formula for spherical harmonics, which serves as an innovative approach to analyzing the NTK. 3. The results are applicable to both shallow and deep networks.

Weaknesses

1. The current results are constrained to scenarios where the activation function is exclusively ReLU, which potentially limits the applicability. What is the primary impediment to generalizing the current results ? 2. The structure of the paper needs to be improved. The main conclusion are presented in Theorem 1 and 8, but it takes a lot of space to present the proof sketch in the corresponding section, more discussions on how the upper/lower bounds influence the performance of the DNNs should be included ? 3. Theorem 8 requires the layer width satisfy a pyramidal condition, I wonder whether modern DNNs architecture fullfills this requirement? 4. I acknowledge the theoretical contributions made by the authors, but I would recommend the authors to add some empirical studies to support their theoretical claims. minors: $X \in \mathbb{R}^{d \times n}$ should be $X \in \mathbb{R}^{d_0 \times n}$

Questions

Please refer to weaknesses

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Reviewer fqQK2024-08-10

Response

Thank you for the rebuttal. My concerns have been well addressed, and I would like to keep my positive score of this paper.

Reviewer NBnj6/10 · confidence 3/52024-07-12

Summary

The paper derives new bounds on the smallest eigenvalue in NTK kernel matrices crucially used in the analyses of neural network training and generalization. Hereby it uses new analytical techniques. One main point improving over most previous bounds is that they are widely distribution independent. The only (standard) assumptions are that data lies on the unit sphere, and they are not too collinear as introduced by Oymak & Soltanolkotabi, 2020. It seems that the new results improve over previous work Banerjee et al., 2023. But I am missing direct comparisons which could be addressed in the rebuttal.

Strengths

* widely distribution independent bounds * only standard assumptions * linear dependence on network width * extension to multilayer NN

Weaknesses

* limited to ReLU activation * missing out some direct comparisons to previous bounds * study is motivated by NN optimization, but only the initialization phase is actually considered

Questions

* how do the new bounds affect the full (S)GD optimization e.g. for squared loss? (for instance while the width is linear for your bounds, many previous analyses require larger polynomial width in the course of optimization, even where low width suffices in the initialization) * how do the new bounds relate to existing bounds for classification under cross entropy loss? For instance the delta dependence that is between linear and quadratic in Thm 1 reminds closely of the results in https://arxiv.org/abs/2206.12802 that are also between linear and quadratic in gamma, the separation margin in NTK for classification (which seems closely related to your delta). * any idea on resolving the linear/quadratic gap?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

-

Reviewer Hffy2024-08-09

Thank you for your answer. After reading the other reviews, I would tend to accept this paper as it makes the first step to bound for the smallest eigenvalue of the NTK with arbitrary input dimension, under the condition that the authors include the discussion in other reviews.

Reviewer qjpA2024-08-09

Thank you for the rebuttal, as indicated in the original review I considered the paper acceptance-worthy anyway. About the $\delta$-uniform-separation versus earlier approaches, after some thought I think that the main question is regarding the counterpart to Corollary 2 obtainable by previous work. Corollary 2 gives one estimate for iid uniform data, but with a nontrivial dependence on a comparison to previous results without passing through $\delta$-separation would make a good addition to the main text. Is it possible to directly compare the bound from this Corollary to what one would get by using prior work? Since the property $P(\delta,\epsilon,n)=$"$\delta$-separation holds with probability $\ge 1-\epsilon$ on a sample on $n$ i.i.d. points in the unit sphere" is true only in a nontrivial shaped region in $(\delta,\epsilon,n)$-space, it's hard (for me, and I'm sure for the average reader) to really check whether your "metric/banach geometry based" result is or is not better than earlier "probabilistic based" results that you cite in the introduction. So my main question on the topic of what I (pompously) called "the main weakness" in the original review is: Is it possible to give a counterpart to the bound of Corollary 2 using the methods from previous works? (if not, I still think the score is above acceptance level anyway)

Reviewer NBnj2024-08-12

Thank you for your response. I am happy to raise my score by one point, conditioned on more thorough discussion to the related work, focusing on similarities, that could potentially benefit either lines of work, rather than focusing on differences in details of their settings

Authorsrebuttal2024-08-13

We thank the reviewer for the discussion and for helping us improve our work. We will gladly endeavor to incorporate the highlighted points into our next revision.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC