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

We are grateful for the positive feedback. In regard to your question,

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

this is an interesting question and one we hope to pursue in future works. In particular, for rotationally invariant distributions reasonable estimates of $\delta$ holding with high probability are relatively easy to derive. For more general distributions however this is more challenging.

We thank the reviewer for their overall positive feedback and are confident we can address each of the concerns raised. In light of our responses below we hope the reviewer will consider increasing their score.

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 order for a dataset to be $\delta$-separated for some value of $\delta\neq 0$, it is sufficient for the data points to not be scalar multiples of one another. Compared to other works, which depend on the data being drawn iid from specific families of high-dimensional probability distributions, we believe that this condition is a relaxation. Note $\delta \neq 0$ is necessary for $\lambda\_{min}>0$. Furthermore, all datasets drawn mutually iid from a continuous distribution are almost surely $\delta$-separated for some $\delta>0$, but not all $\delta$-separated datasets must be drawn mutually iid from some high distribution. Of course, the strength of our results depends on the actual amount of separation between data points, however we remark that this issue is also implicitly present for the prior works, e.g., they require $d = \Omega(\log(n))$. We remark that our goal in including Corollary 2 was to give a sense of the implications of this assumption for a specific probability distribution. We will make this point more clear in the final version.

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.

There could indeed be challenges in computing good bounds for $\delta$ for which certain probability distributions are $\delta$-separated with high probability. Improving the dependence of our bounds on the $\delta$ particularly with regards to Theorem 8 is an important avenue for future work.

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.

Thank you for pointing this out. We will emphasize that our notion of $\delta$-separatedness is different from definitions used in some other works. We decided to use this terminology following Assumption 1 of [1].

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

Thank you for highlighting this potential source of confusion, we will seek to rectify this point in future revisions of the paper.

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}$.

Thanks for noting this typo. We will fix it in the final version.

Section 2 has a large overlap with the introduction. Could it be shortened or merged?

Thanks for the feedback. Section 2 provides a background and deep dive on the results in related work, the Introduction was intended to introduce and motivate the topic. In particular, we felt it important to clarify the contributions of this work versus that of Bombari et al and Nguyen et al. However, we will certainly look at ways to shorten and combine both sections.

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 \in \mathbb{R}^3$ affects the constant from Theorem 1.

The purpose of this comment was to address the constraint $d \geq 3$ in Theorem 1. In principle, one could take data in 1 or 2 dimensions and pad it with zeros so that it lies in $\mathbb{S}^2$ and Theorem 1 applies. All other aspects of the theorem would be unaffected, including the constant $\delta'$. This is not a particularly interesting case, but we mentioned it for the sake of completeness.

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.

We will clarify this point in the final version.

[1] Oymak, Samet, and Mahdi Soltanolkotabi. "Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks." IEEE Journal on Selected Areas in Information Theory 1.1 (2020): 84-105.

We thank the reviewer for their positive feedback and thoughtful comments. We are confident that we can address your concerns and hope in light of our responses the reviewer might consider increasing their score.

The current results are constrained to scenarios where the activation function is exclusively ReLU, which potentially limits the applicability

We do indeed restrict ourselves to the ReLU activation. There are a couple of places where ReLU plays an important role in our proofs, which may shed light on generalizations to other activations. First, we use the scale-invariance of ReLU to reduce expectations over Gaussian measures to expectations over the sphere, as in Lemmas 3 and 4. As we remark after the statements of these lemmas, this reduction allows us to work with integrals over the sphere and spherical harmonics, for which there is an abundance of theory we can port over. For non-homogeneous activation functions, we suspect that one could apply similar results from harmonic analysis on $L^2(\mathbb{R}^d, \nu)$ in place of $L^2(\mathbb{S}^{d - 1})$ (where $\nu$ is a Gaussian probability measure). Second, our bounds rely on computing Fourier coefficients for ReLU in Lemmas 20 and 21. One could compute coefficients in a similar manner for other specific activation functions such as leaky ReLU or polynomials, but in general computing these integrals exactly is not feasible. A possible solution is to bound the integrals in terms of $r, d$, and regularity properties of the activation.

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

We are happy to receive any feedback or ideas as to how the presentation and content of the paper can be improved and will incorporate it into any revised version. Currently we summarize both Theorem 1 and 8 in the introduction in order to give the reader an overview of our contributions straight away. Our key technical innovations are for shallow networks in Section 3, which we then extend to deep networks using more standard techniques in Section 4. As a result we spend significant space describing these new techniques in Section 3. In general, as the key contributions of this paper are theoretical in nature we wanted to provide detailed proof sketches.

Theorem 8 requires the layer width satisfy a pyramidal condition, I wonder whether modern DNNs architecture fulfills this requirement

The reviewer correctly points out that the strict pyramidal assumption does not necessarily hold in practice. However, given our key technical innovations are for shallow networks, we chose to adopt this assumption for simplicity in order to highlight a way in which our results can be extended to cover deep networks. We note that the strict pyramidal condition is convenient as it allows us to easily bound products involving factors of the form $\sqrt{d_l} + \sqrt{d\_{l-1}}$, however this condition could likely be relaxed to a weak pyramidal condition or potentially removed altogether.

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

We thank the reviewer for their overall positive feedback on our work. We are confident that we are able to address your concerns and hope in light of our responses below that you might consider raising your score. First in regards to the highlighted weaknesses we offer the following comments.

limited to ReLU activation

We do indeed restrict ourselves to the ReLU activation. There are a couple of places where ReLU plays an important role in our proofs, which may shed light on generalizations to other activations. First, we use the scale-invariance of ReLU to reduce expectations over Gaussian measures to expectations over the sphere, as in Lemmas 3 and 4. As we remark after the statements of these lemmas, this reduction allows us to work with integrals over the sphere and spherical harmonics, for which there is an abundance of theory we can port over. For non-homogeneous activation functions, we suspect that one could apply similar results from harmonic analysis on $L^2(\mathbb{R}^d, \nu)$ in place of $L^2(\mathbb{S}^{d - 1})$ (where $\nu$ is a Gaussian probability measure). Second, our bounds rely on computing Fourier coefficients for ReLU in Lemmas 20 and 21. One could compute coefficients in a similar manner for other specific activation functions such as leaky ReLU or polynomials, but in general computing these integrals exactly is not feasible. A possible solution is to bound the integrals in terms of $r, d$, and regularity properties of the activation.

missing out some direct comparisons to previous bounds

In the related works Section 2 of the paper we highlight Nguyen et al. and Bomari et al. as the most relevant works and discuss the bounds they provide. We emphasize that these bounds are hard to compare like-for-like as they hold / are non-vacuous under different assumptions. Our work provides bounds on the smallest eigenvalue of the NTK in a more general setting than the prior works with respect to two important aspects: first and unlike prior works we make no distributional assumptions on the data, instead we express our bounds in terms of the smallest difference between two points. Second we do not require the input dimension to scale with the number of samples; prior works cannot cover this classical statistical setting. In particular, as long as the first two layer widths satisfy $d\_0d\_1 = \Omega(n^{1 + 4/(d\_0-1)})$ then $\lambda\_{\min} = \Omega(n^{- 4/(d\_0-1)})$ with high probability. This bound holds as long as $d\_0\geq 3$ and furthermore if $d_0 = \Omega(\log(n))$ then it is tight up to logarithmic factors and matches the bounds provided in the prior works (which require $d\_0 = \Omega(\log(n))$ to hold in the first place).

study is motivated by NN optimization, but only the initialization phase is actually considered.

To recap the standard procedure for proving global optimization guarantees via the NTK: 1) bound the distance from the parameters to their position at initialization throughout training using a real induction argument, 2) use the previous step to lower bound the smallest eigenvalue of the NTK at any time $t$ in terms of the value of the smallest eigenvalue at initialization, 3) lower bound the smallest eigenvalue of the NTK at initialization. Our work covers step 3 and is therefore a key ingredient of this pipeline for proving global convergence guarantees.

Next, in regard to the 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)

The reviewer correctly points out that the key bottleneck in terms of width requirements originates from the real inductive step used to ensure the network parameters remain in some ball around their initialization. Therefore, even if linear width suffices to bound the smallest eigenvalue of the NTK at initialization one still requires polynomial width to use this to lower bound the smallest eigenvalue of the NTK throughout training. However, even with polynomial width, without a quantitative lower bound on the smallest eigenvalue of the NTK at initialization it is not possible to provide a quantitative bound on the rate of convergence. Our work provides such a bound and does so under general assumptions on the input data, thereby extending the applicability of the framework as a whole.

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?

The work referenced by the reviewer shows for a two-layer ReLU network that when running gradient descent on binary classification using a coupled initialization technique, width $m = O(\gamma^{-2} \log n)$ suffices to achieve arbitrarily small training error and $m =\Omega(\gamma^{-1})$ is necessary, where $\gamma$ is a quantity that determines the separation margin of the NTK. Their discussion indicates that the coupled initialization is a key ingredient allowing them to reduce width requirements to $m=\Omega(\gamma^{-2}\log n)$ when bounding the logistic loss averaged over $T$ gradient descent iterations. Thus there appear to be differences in the settings (coupled initialization), objects originating the width requirements (loss along gradient descent), as well as in the considered quantities (separation margin of the NTK). Nonetheless, we agree that exploring possible connections between the linear and quadratic dependencies might be interesting and thank the reviewer for the pointer.