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

Authors: kedar  karhadkar
michael  murray
guido  montúfar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:04:56

Abstract: 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 distance between data points: 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.

Main paper: 
 introduction: 
 A popular approach for studying the optimization dynamics of neural networks is analyzing the neural tangent kernel (NTK), which corresponds to the Gram matrix obtained from the Jacobian of the network parametrization map (Jacot et al., 2018) . When the network parameters are adjusted by gradient descent, the network function follows a kernel gradient descent in function space with respect to the NTK. By bounding the smallest eigenvalue of the NTK away from zero it is possible to obtain global convergence guarantees for gradient descent parameter optimization (Du et al., 2019b; Oymak & Soltanolkotabi, 2020) as well as results on generalization (Arora et al., 2019a; Montanari & Zhong, 2022) and data memorization capacity (Montanari & Zhong, 2022; Nguyen et al., 2021; Bombari et al., 2022) . These key advances highlight the importance of deriving tight, quantitative bounds for the smallest eigenvalue of the NTK at initialization. While initial breakthroughs on the convergence of gradient optimization in neural networks (Li & Liang, 2018; Du et al., 2019a; Allen-Zhu et al., 2019) required unrealistic conditions on the width of the layers, subsequent and substantive efforts have reduced the level of overparametrization required to ensure that the NTK is well conditioned at initialization (Zou & Gu, 2019; Oymak & Soltanolkotabi, 2020) . In particular, Nguyen (2021) ; Nguyen et al. (2021) ; Banerjee et al. (2023) showed that layer width scaling linearly in the number of training samples n suffices to bound the smallest eigenvalue and Montanari & Zhong (2022) ; Bombari et al. (2022) obtained results for networks with sub-linear layer width and the minimum possible number of parameters Ω(n) up to logarithmic factors. However, and as discussed in Section 2, the bounds provided in prior works require that the data is drawn from a distribution satisfying a Lipschitz concentration property, and only hold with high probability if the input dimension d 0 scales as √ n (Bombari et al., 2022) or polylog(n) (Nguyen et al., 2021) . These existing results therefore require that the dimension of the data grows unbounded as the number of training samples n increases and as such there is a gap in our understanding of cases where the data is sampled from a fixed, or lower-dimensional space.In this work we present new lower and upper bounds on the smallest eigenvalue of a randomly initialized, fully connected ReLU network: compared with prior work, our results hold for arbitrary data on a sphere of arbitrary dimension. Our techniques are novel and rely on the hemisphere transform as well as the addition formula for spherical harmonics.We study neural networks denoted as functions f : R d0 × P → R, where P is an inner product space. To be clear, f (x; θ) denotes the output of the network for a given input x ∈ R d0 and parameter choice θ ∈ P. For brevity we occasionally write f (x) in place of f (x; θ) if the context is clear. We use n to denote the size of the training sample, d 0 the dimension of the input features, L the network depth, d l the width of the lth layer and σ : R → R the ReLU activation function. Given n input data points x 1 , • • • , x n ∈ R d0 we write X = [x 1 , • • • , x n ] ∈ R d0×n and define F : P → R n to be the evaluation of the network on these n data points as a function of the parameter θ,F (θ) = [f (x 1 ; θ), • • • , f (x n ; θ)] T .We define the neural tangent kernel (NTK) of F asEQUATIONwhere the gradient ∇ and adjoint * are taken with respect to the inner product on P and the Euclidean inner product on R n . More explicitly [K(θ)] ik = ⟨∇ θ f (x i ; θ), ∇ θ f (x k ; θ)⟩. For convenience we write K in place of K(θ). We are concerned with the minimum eigenvalue λ min (K), which depends both on the input data X and the parameter θ. We say the dataset x 1 , • • • , x n is δ-separated for δ ∈ (0, √ 2] if min i̸ =k min(∥x i -x k ∥, ∥x i + x k ∥) ≥ δ, which is a measure of distance in direction.Main contributions. Our results are for data that lies on a sphere and is δ-separated for some δ ∈ (0, √ 2]. Unlike prior work we do not make any assumptions on the distribution from which the data is sampled, e.g., uniform on the sphere or Lipschitz concentrated, and we do not require the input dimension d 0 to scale with the number of samples n.• In Theorem 1 we consider shallow ReLU networks with input dimension d 0 and hidden width d 1 and prove that if d 1 = Ω(∥X∥ 2 d 3 0 δ -2 ) then with high probability λ min (K) = Ω(d -3 0 δ 2 ). Furthermore, defining δ ′ = min i̸ =k ∥x i -x k ∥, we have λ min (K) = O(δ ′ ).• In Theorem 8 we illustrate how our results for shallow networks can be extended to cover depth-L networks. In particular, if the layer widths satisfy a pyramidal condition, meaning d l ≥ d l+1 for l ∈ {1, • • • , L -1}, d L-1 ≳ 2 L log(nL/ϵ) and d 1 = Ω(nd 3 0 δ -4 ), then λ min (K) = Ω(d -3 0 δ 4 ) and λ min (K) = O(L) with high probability. • Our results allow us to analyze the smallest eigenvalue of the NTK for data drawn from any distribution for which one can establish δ-separation with high probability in terms of d 0 and n. For example, for shallow networks with data drawn uniformly from a sphere, in Corollary 2 we show that if d 0 d 1 = Ω(n 1+4/(d0-1) ), then with high probability λ min (K) = Õ n -2/(d0-1) and λ min (K) = Ω n -4/(d0-1) . Moreover, this bound is tight up to logarithmic factors for d 0 = Ω(log(n)) matching prior findings for this regime.The rest of this paper is structured as follows: in Section 2 we provide a summary of related works and compare and contrast our results with the existing state of the art; in Section 3 we present our results for shallow networks; finally in Section 4 we extend our shallow results to the deep case.Notations. With regard to general points on notation we let [n] = {1, 2, • • • , n} denote the set of the first n positive integers. If x ∈ R d then we let [x] i denote the ith entry of x. If f and g are real-valued functions, we write f ≲ g or f = O(g) when there exists an absolute constant C such that f (x) ≤ Cg(x) for all x. Similarly, we write f ≳ g or f = Ω(g) when there exists a constant c such that f (x) ≥ cg(x) for all x. We write f ≍ g when f ≲ g and f ≳ g both hold. The notation Ω hides logarithmic factors. Logarithms are generally considered to be in base e, though in most settings the particular choice of base can be absorbed by a constant. 
related work: 
 Prior work on the NTK. Jacot et al. (2018) highlight that the optimization dynamics of neural networks are controlled by the Gram matrix of the Jacobian of the network function, an object referred to as the NTK Gram matrix, or, as we refer to it here, simply the NTK. That work also shows that in the infinite-width limit the NTK converges in probability to a deterministic kernel. Of particular interest is the observation that in the infinite-width setting the network behaves like a linear model (Lee et al., 2019) . Further, if a network is polynomially wide in the number of samples then the smallest eigenvalue of the NTK can be lower bounded in terms of the smallest eigenvalue of its infinite-width analog. As a result, assuming the latter is positive, global convergence guarantees for gradient descent can be obtained (Du et al., 2019a,b; Allen-Zhu et al., 2019; Zou & Gu, 2019; Lee et al., 2019; Oymak & Soltanolkotabi, 2020; Zou et al., 2020; Nguyen & Mondelli, 2020; Nguyen, 2021; Banerjee et al., 2023) . The positive definiteness of the NTK is equivalent to the Jacobian having full rank, which can also be used to study the loss landscape (Liu et al., 2020 (Liu et al., , 2022;; Karhadkar et al., 2023) . Beyond the smallest eigenvalue, there is interest in characterizing the full spectrum of the NTK (Basri et al., 2019; Geifman et al., 2020; Fan & Wang, 2020; Bietti & Bach, 2021; Murray et al., 2023) , which has implications on the dynamics of the empirical risk (Arora et al., 2019b; Velikanov & Yarotsky, 2021) as well as the generalization error (Cao et al., 2021; Basri et al., 2020; Cui et al., 2021; Jin et al., 2022; Bowman & Montúfar, 2022) . Finally, although a powerful and successful tool for analyzing neural networks it must be noted that the NTK has limitations, most notably perhaps that it struggles to explain the rich feature learning commonly observed in practice (Lee et al., 2020a; Chizat et al., 2019; Liu et al., 2020) .Prior work on the smallest eigenvalue of the NTK. Many of the prior works discussed so far assume or prove that λ min (K) is positive, but do not provide a quantitative lower bound. Here we discuss works seeking to address this issue and to which we view our work as complementary. For shallow ReLU networks and data drawn uniformly from the sphere, Xie et al. (2017, Theorem 3) and Montanari & Zhong (2022, Theorem 3. 2) provide lower bounds on the smallest singular and eigenvalue value of the Jacobian and NTK respectively. In addition to requiring the data to be drawn uniform from the sphere both of these results are high dimensional in the sense that for Xie et al. (2017, Theorem 3 ) to be non-vacuous it is necessary thatd 0 = Ω(d 1 n 2 ), while Montanari & Zhong (2022, Theorem 3.2) requires, as per their Assumption 3.1, that d 0 = Ω( √ n).Nguyen et al. (2021, Theorem 4.1) derives lower and upper bounds for the smallest eigenvalue of the NTK for deep ReLU networks under standard initialization conditions assuming the data is drawn from a distribution satisfying a Lipschitz concentration property. They show that the NTK is well conditioned if the network has a layer of width of order equal to the number of data points n up to logarithmic factors. Concretely, if at least one layer has width linear in n (ignoring logarithmic factors) and the others are at least poly-logarithmic in n, then λ min (K) = Ω(µ 2 r (σ)d 0 ) (or Ω(µ 2 r (σ)) with normalized data), where µ r (σ) denotes the rth Hermite coefficient of σ with any even integer r ≥ 2. However, in their result the bound holds with high probability only if d 0 scales as log(n). Bombari et al. (2022, Theorem 1) derive lower and upper bounds for the smallest eigenvalue of the NTK under similar conditions as Nguyen et al. (2021, Theorem 4 .1) aside from the following: they consider smooth rather than ReLU activation functions, the widths follow a loose pyramidal topology, meaningd l = O(d l-1 ) for all l ∈ [L -1], d L-1 d L-2scales linearly in n (ignoring logarithmic factors), and there exists a γ > 0 such that n γ = O(d L-1 ). Under these conditions they show that λ min (K) = Ω(d L-1 d L-2 ) with high probability as both d L-1 and n grow. This result illustrates that for the NTK to be well conditioned it suffices that the number of neurons grows as Ω( √ n). The loose pyramidal condition on the widths impliesd L-1 d L-2 = O(d 2 0) and as they also assume thatn = o(d L-1 d L-2 ) then n = o(d 2 0 ) which in turn implies d 0 = Ω( √ n).The rough strategy used by both Bombari et al. (2022) and Nguyen et al. (2021) , as well as in our own results, can be described in terms of two main steps. In the first step, one bounds the smallest eigenvalue of a shallow network. The results for the shallow case can then be extended to the deep case, e.g., via a layerwise decomposition of the NTK matrix. This second step is architecture-dependent and its proof depends on the bounds derived in the first step. Our results focus on improving the first step which imply corresponding improvements for the second step. 
shallow networks: 
 Here we study the smallest eigenvalue of the NTK of a shallow neural network. The parameter space P of this network is R d1×d0 × R d1 and it is equipped with the inner product⟨(W , v), (W ′ , v ′ )⟩ = Trace(W T W ′ ) + v T v ′ .For convenience we sometimes write d = d 0 . The neural network f : R d0 × P → R is defined asEQUATIONwhereW = [w 1 , • • • , w d1 ] T ∈ R d1×d0 are the inner layer weights, v = [v 1 , • • • , v d1 ] T ∈ R d1the outer layer weights, and θ = (W , v). We consider the ReLU activation function applied entrywise with σ(z) = max{0, z}. The derivative σ satisfies σ(z) = 1 for z > 0 and σ(z) = 0 for z < 0. Although σ is not differentiable at 0, we take σ(0) = 0 by convention. Unless otherwise stated we assume that the entries of W and v are drawn mutually iid from a standard Gaussian distribution N (0, 1). Our main result for shallow networks is the following theorem.Theorem 1. Let d ≥ 3, ϵ ∈ (0, 1), and δ, δ ′ ∈ (0, √ 2). Suppose that x 1 , • • • , x n ∈ S d-1 are δ-separated and min i̸ =k ∥x i -x k ∥ ≤ δ ′ . Define λ = 1 + d log(1/δ) log(d) -3 δ 2 . If d 1 ≳ ∥X∥ 2 λ log n ϵ , then with probability at least 1 -ϵ, λ ≲ λ min (K) ≲ δ ′ . A proof of Theorem 1 is provided in Appendix C.7. Suppressing logarithmic factors, Theorem 1 implies that d 1 = Ω ∥X∥ 2 d 3 0 δ -2 suffices to ensure that λ min (K) = Ω(d -3 0 δ 2 ) and λ min (K) = O(δ ′ ) with high probability (note the trivial bound ∥X∥ 2 ≤ ∥X∥ 2 F ≤ n).We emphasize that unlike existing results i) we make no distributional assumptions on the data, instead only assuming a milder δ-separated condition, and ii) our bounds hold with high probability even if d 0 is held constant.A few further remarks are in order. First, the condition d 0 ≥ 3 is necessary because our technique relies on the addition formula for spherical harmonics (Efthimiou & Frye, 2014, Theorem 4.11) ; the bound we derive based on this formula (Lemma 15 in Appendix A.2) becomes vacuous for d 0 < 3. However, for d 0 = 2 analogous bounds could be derived using more elementary tools while the case d 0 = 1 is of little interest as only a trivial dataset is possible. Moreover, data in S 1 could be embedded in S 2 since we do not impose any distributional assumptions.Second, one can use Theorem 1 to bound the smallest eigenvalue of the NTK for data drawn from the uniform distribution on the sphere by bounding δ with high probability in terms of n and d. We use that δ = Ω(n -2/d0 ) and δ ′ = O(n -2/d0 ) with high probability. We direct the interested reader to Appendix C.8 for further details.Corollary 2. Let d ≥ 3, n ≥ 2, ϵ ∈ (0, 1), x 1 , • • • , x n ∼ U (S d-1 ) be mutually iid. Define λ = 1 + log(n/ϵ) log(d) -3 ϵ 2 n 4 1/(d-1).If d 1 ≳ 1 λ 1 + n+log(1/ϵ) dlog n ϵ , then with probability at least 1 -ϵ over the data and network parameters,λ ≲ λ min (K) ≲ log(1/ϵ) n 2 1/(d-1).The above corollary implies that if d 0 d 1 = Ω n 1+4/(d0-1) , then with high probability λ min (K) = Ω(n -4/(d0-1) ) and λ min (K) = Õ(n -2/(d0-1) ). In particular, for data sampled uniformly from a sphere, the scaling d 0 = Ω(log n) is both necessary and sufficient for λ min (K) to be Θ(1). In particular the bounds are sharp in this case.Recall the definitions of F (θ) and K in (1). For the choice of f given in (2), a straightforward decomposition of the NTK with respect to the inner and outer weights givesEQUATIONwhereK 1 = ∇ W F (θ) * ∇ W F (θ) and K 2 = ∇ v F (θ) * ∇ v F (θ) = 1 d1 σ(W X) T σ(W X). As both K 1 and K 2 are positive semi-definite, λ min (K) ≥ λ min (K 1 ) + λ min (K 2 );(4) see, e.g., Horn & Johnson (2012, Theorem 4.3.1) . Our proof now follows the highlighted steps below.1) Bound the smallest eigenvalue in terms of the infinite-width limit. We proceed to bound both λ min (K 1 ) and λ min (K 2 ) in terms of the smallest eigenvalues of their infinite-width counterparts, see Lemmas 3 and 4 below, which act as good approximations for sufficiently wide networks.Lemma 3. Suppose that x 1 , • • • , x n ∈ S d-1 . Let λ 1 = λ min E u∼U (S d-1 ) σ X T u σ u T X . If λ 1 > 0 and d 1 ≳ λ -1 1 ∥X∥ 2 log n ϵ , then with probability at least 1 -ϵ λ min (K 1 ) ≳ λ 1 . Lemma 4. Suppose that x 1 , • • • , x n ∈ S d-1 . Let λ 2 = dλ min E u∼U (S d-1 ) σ(X T u)σ(u T X) .If λ 2 > 0 and d 1 ≳ n λ2 log n λ2 log n ϵ , then with probability at least 1 -ϵλ min (K 2 ) ≳ λ 2 .We prove Lemmas 3 and 4 in Appendices C.1 and C.2 respectively. Observe that while the parameters of the model are initialized as Gaussian, the expectations above are taken with respect to the uniform measure on the sphere. The motivation for using the uniform measure on the sphere is that it enables us to work with spherical harmonics, for which there is the highly useful addition formula (see, e.g., Efthimiou & Frye, 2014, Theorem 4.11) . The exchange of measures is possible in the case of Lemma 3 due to the scale invariance of σ, while for Lemma 4 it is possible because σ is homogeneous.2) Interpret the infinite-width kernel in terms of a hemisphere transform. Next, for a given X and ψ ∈ { √ dσ, σ} we define the limiting NTK K ∞ ψ ∈ R n×n asEQUATIONConsider a fixed vector z ∈ S n-1 and interpret the Euclidean inner product ⟨ψ(X T u), z⟩ as a function of u ∈ S d-1 . It will prove useful to think of this map as an integral transform. To this end let M(S d-1 ) denote the vector space of signed Radon measures on S d-1 and fix ψ ∈ { √ dσ, σ}. For a signed Radon measure µ ∈ M(S d-1 ) we introduce the integral transform T ψ µ : S d-1 → R, defined asEQUATIONNote for ψ ∈ { √ dσ, σ} this is a hemisphere transform (Rubin, 1999) as the integrand ψ(⟨u, •⟩) is supported on a hemisphere normal to u. We provide background material on the hemisphere transform in Appendix B. Let M X ⊂ M denote the space of signed Radon measures supported on the data set {x 1 , • • • , x n }. For each measure µ ∈ M X there exists a vector z ∈ R n such that µ = n i=1 z i δ xi , where δ x is the Dirac measure supported on x. We write µ = µ z to indicate this correspondence. The following lemma relates the smallest eigenvalue of K ∞ ψ to the norm of the hemisphere transform of a measure supported on the data; a proof is provided in Appendix C.3.Lemma 5. Fix X ∈ R d×n and ψ ∈ { √ dσ, σ}. For all z ∈ R n , ⟨K ∞ ψ z, z⟩ = ∥T ψ µ z ∥ 2 . Moreover, λ min (K ∞ ψ ) = inf ∥z∥=1 ∥T ψ µ z ∥ 2 .3) Bound the hemisphere transform norm via spherical harmonics. We proceed to lower bound ∥T ψ µ z ∥ 2 for all z ∈ R d . Let L 2 (S d-1 ) denote the Hilbert space of real-valued, square-integrable functions with respect to the uniform probability measure on S d-1 , and let C(S d-1 ) ⊂ L 2 (S d-1 ) denote the subspace of continuous functions. For µ ∈ M(S d-1 ) and g ∈ C(S d-1 ) we define ⟨µ, g⟩ :=S d-1 g(x)dµ(x). If g 1 , • • • , g N ∈ L 2 (S d-1) are orthonormal, in particular consider g r as spherical harmonics, then via a Bessel inequality∥T ψ µ z ∥ 2 ≥ N a=1 |⟨T ψ µ z , g a ⟩| 2 = N a=1 |⟨µ z , T ψ g a ⟩| 2 = N a=1 n i=1 (T ψ g a )(x i )z i 2 .Importantly, T ψ is self-adjoint (see Lemma 17 in Appendix B for details) and the spherical harmonics are eigenfunctions of T ψ , i.e., T ψ g a = κ a g a . A summary of the key properties of spherical harmonics needed for our results are provided in Appendix A.2. Therefore∥T ψ µ z ∥ 2 ≥ N a=1 n i=1 (T ψ g a )(x i )z i 2 = N a=1 κ 2 a n i=1 g a (x i )z i 2 ≥ min a κ 2 a ∥Dz∥ 2 2 ,where D ∈ R N ×n is a matrix with entries [D] ai = g a (x i ). As a resultλ min (K ∞ ψ ) ≥ min a κ 2 a σ 2 min (D).4) Bound the hemisphere transform and spherical harmonics on the data. The following result shows that if we let the functions (g a ) a∈[N ] be spherical harmonics and allow N to be sufficiently large, then we can bound the minimum singular value of D. In what follows let H d r denote the vector space of degree-r harmonic homogeneous polynomials on d variables. Lemma 6. Supposex 1 , • • • , x n ∈ S d-1 are δ-separated. Suppose that β ∈ {0, 1} and that R ∈ Z ≥0 are such that N := R r=0 dim(H d 2r+β ) satisfies N ≥ C δ 4 2 -(d-2)/2where C > 0 is a universal constant. Let g 1 , • • • , g N be spherical harmonics which form an orthonormal basis ofR r=0 H d 2r+β . If D ∈ R N ×n is defined as D ai = g a (x i ) then σ min (D) ≥ N 2 .A proof of Lemma 6 can be found in Appendix C.4. By carefully choosing values for R and N in Lemma 6 and performing some asymptotics on the resulting expressions, we arrive at the following bound on the hemisphere transform of a measure. Lemma 7. Let d ≥ 3 and suppose thatx 1 , • • • , x n ∈ S d-1 are δ-separated. For all z ∈ R n with ∥z∥ ≤ 1 then ∥T ψ µ z ∥ 2 ≳      1 + d log(1/δ) log d -3 δ 2 if ψ = σ 1 + d log(1/δ) log d -3 δ 4 if ψ = √ dσ.A proof of Lemma 7 is provided in Appendix C.5. The lower bound of Theorem 1 follows by bounding λ 1 , as defined in Lemma 3, using Lemma 7.Before proceeding to the upper bound, we pause to remark on the generality of this argument for handling other activation functions. First, we use the positive homogeneity of the activation function in order to write λ min (K ∞ ψ ) as the L 2 (S d-1 ) norm of a function on the sphere. This is beneficial as it allows us to work with the spherical harmonics and use the associated addition formula. The ReLU activation and its derivative are also convenient with regard to computing the eigenvalues of the hemisphere transform (or more generally the eigenvalues of the integral operator). In particular, this requires evaluating integrals against Gegenbauer polynomials for which analytic expressions are available. For polynomial or piecewise polynomial activations similar results could be obtained. However, for other activations, e.g., tanh or sigmoid, such quantities appear challenging to compute.5) Upper bound. The upper bound of Theorem 1 is simpler than the lower bound and hinges on the following calculation. Let x i , x k be two data points. Thenλ min (K) ≤ 1 2 (e i -e k ) T K(e i -e k ) = 1 2 ∥∇ θ f (x i ) -∇ θ f (x k )∥ 2 .Therefore it suffices to upper bound the norm of∇ θ f (x i ) -∇ θ f (x k ). We choose i, k ∈ [n]such that x i , x k are the two closest points in the dataset. We then translate this into a statement about the gradients. If ∥x i -x k ∥ ≤ δ, then with high probability over the network parameters,∥∇ θ f (x i )-∇ θ f (x k )∥ 2 ≲ δ (see Lemma 29), and we arrive at the desired upper bound in Theorem 1.4 From shallow to deep neural networksOur goal here is to detail just one approach as how the results of Section 3 can be extended to deep networks. To be clear, here we consider a fully connected network with input dimension d 0 and L layers, where each layer has width d 1 , • • • , d L respectively and d L = 1. The parameter space P is a product space of matrices L l=1 R d l ×d l-1 , equipped with the inner product⟨(W 1 , • • • , W L ), (W ′ 1 , • • • , W ′ L )⟩ = L l=1 Trace(W T l W ′ l ).The feature maps f l : R d0 × P → R d l of the neural network are given byf l (x; θ) =    x l = 0 σ(W l f l-1 (x; θ)) l ∈ [L -1] W l f l-1 (x; θ) l = L,whereW l ∈ R d l ×d l-1 for all l ∈ [L], θ = (W 1 , • • • , W L )and σ is the ReLU function x → max(0, x) applied elementwise. We define the network map f to be the final feature map multiplied by a normalizing constant:EQUATIONGiven n data points x 1 , • • • , x n , we bound the smallest eigenvalue of the NTK (1) associated with this particular choice of f . Theorem 8. Suppose ϵ∈ (0, 1/3), δ ∈ (0, √ 2], d 0 ≥ 3, the data x 1 , x 2 , • • • , x n ∈ S d0-1 is δ-separated and define λ = 1 + d 0 log(1/δ) log d 0 -3 δ 4 .With regard to the network architecture, letL ≥ 3, d l ≥ d l+1 for all l ∈ [L-1], d L-1 ≳ 2 L log nL ϵ and d 1 ≳ n λ log n λ log n ϵ .Then with probability at least 1 -ϵ over the network parameters λ ≲ λ min (K) ≲ L.We emphasize that these bounds make no distributional assumptions on the data other than lying on the sphere and being δ-separated; in particular, they hold even for constant d 0 . Indeed, if we consider d 0 as some constant then Theorem 8 implies that if the first layer is sufficiently wide, d 1 = Ω(nδ -4 ), then with high probability over the parameters λ min (K) = Ω(δ 4 ) and λ min (K) = O(1).A few remarks are in order. First, the pyramidal condition on the network widths could be relaxed by more directly borrowing techniques from Nguyen et al. (2021) . We adopt this condition as it has the advantage of making the dependence of our bounds on the network depth L clearer. Second, compared with Theorem 1 and ignoring log factors, we observe the lower bound differs by a factor of δ 2 . This arises as a result of the smallest eigenvalue of the feature Gram matrix F T 1 F 1 being equivalent to the Jacobian of a shallow network with respect to the second layer weights, not the inner layer weights, which has a different lower bound as per Lemma 7. For reasons apparent in the proof outline below the lower bound on λ min (K) lacks a dependency on L, however we hypothesize it should also grow linearly with L thereby matching the dependency of the upper bound. Finally, the upper bound itself follows a similar approach as used by Nguyen et al. (2021) and is weak in the sense that we cannot take advantage of the dataset separation for gradients deeper into the network. We remark that this is also a common problem in the prior work of Nguyen et al. (2021) and Bombari et al. (2022) , we refer the reader to the proof outline below for further details. 
proof outline for theorem 8: 
 The proof of the deep case is structured around the decomposition of the NTK provided in Lemma 9 below. To state this decomposition we introduce the following quantities. For l ∈ [L -1] we define the feature matrices F l ∈ R d l ×n byF l = [f l (x 1 ), • • • , f l (x n )]. For l ∈ [L -1] and x ∈ R d we define the activation patterns Σ l (x) ∈ {0, 1} d l ×d l to be the diagonal matrices Σ l (x) = diag( σ(W l f l-1 (x))).Finally, we let 1 n denote the vector of all ones in R n .Lemma 9. Let x 1 , • • • , x n ∈ R d be nonzero. There exists an open set U ⊂ P of full Lebesgue measure such that f (x i ; •) is continuously differentiable on U for all i ∈ [n]. Moreover, for all θ ∈ U the NTK Gram matrix K defined in (1) with network function (7) satisfies L-1 l=1 d l 2 K= L-1 l=0 (F T l F l ) ⊙ (B l+1 B T l+1 ),where the ith row of B l ∈ R n×n l is defined as[B l ] i,: = Σ l (x i ) L-1 k=l+1 W T k Σ k (x i ) W T L , l ∈ [L -1], 1 n , l = L.For completeness we prove Lemma 9 in Appendix D.1. Observe each matrix summand in Lemma 9 is positive semi-definite (PSD) and recall for any two PSD matrices A and B one has (Schur, 1911) . Thereforeλ min (A + B) ≥ λ min (A) + λ min (B) (see e.g. Horn & Johnson, 2012, Theorem 4.3.1) and λ min (A ⊙ B) ≥ λ min (A) min i∈[n] [B] iiL-1 l=1 d l 2 λ min (K) ≥ L-1 l=0 λ min (F T l F l ) ⊙ (B l+1 B T l+1 ) ≥ λ min F T 1 F 1 min i∈[n] ∥[B 2 ] i,: ∥ 2 .In order to upper bound the smallest eigenvalue we follow Nguyen et al. (2021) and analyze the Raleigh quotient R(u) = u T Ku ∥u∥ 2 . In particular, for any nonzero u ∈ R n we haveλ min (K) ≤ R(u) and therefore λ min (K) ≤ R(e i ) = [K] ii for all i ∈ [n]. As a result L-1 l=1 d l 2 λ min (K) ≤ L-1 l=0 (F T l F l ) ⊙ (B l+1 B T l+1 ) ii = L-1 l=0 ∥f l (x i )∥ 2 ∥[B l+1 ] i,: ∥ 2 .Combining the upper and lower bounds we haveEQUATION)where the right hand side holds for any i ∈ [n]. Based on (8), we proceed first by bounding the norm of the network features. We achieve this via an inductive argument, bounding the norm of the features at one layer with high probability, and then conditioning on this event to bound the norm of the features at the next layer with high probability.Lemma 10. Let x ∈ S d0-1 , L ≥ 2 and l ∈ [L -1]. If d k ≳ l 2 log(l/ϵ) for all k ∈ [l], then e -1 l h=1 d h 2 ≤ ∥f l (x)∥ 2 ≤ e l h=1 d h 2holds with probability at least 1 -ϵ over the network parameters.A proof of Lemma 10 is provided in Appendix D.2. Next we derive upper and lower bounds on the backpropagation terms [B l ] i,: . Our strategy for this is as follows:for l ∈ [L -2], let S l (x) = Σ l (x) L-1 k=l+1 W T k Σ k (x) and observe [B l ] i,: = S l (x i )W T L . Since x i ∈ S d0-1 , it is sufficient to lower bound ∥S l (x)W T L ∥ 2 2 for an arbitrary x ∈ S d0-1 . As the vector W T L ∈ R d L-1 is distributed as W T L ∼ N (0 d L-1 , I d L-1), following Vershynin (2018, Theorem 6.3.2) we have that for any A ∈ R d l ×d L-1 and t ≥ 0P(|∥AW T L ∥ -∥A∥ F | ≥ t) ≤ 2 exp - Ct 2 ∥A∥ 2 for some constant C > 0. As a result, with t = 1 2 ∥A∥ 2 F then P 1 4 ∥A∥ 2 F ≤ ∥AW T L ∥ 2 ≤ 3 4 ∥A∥ 2 F ≥ 1 -exp -C ∥A∥ 2 F ∥A∥ 2 .In order to lower bound ∥S l (x)W T L ∥ 2 with high probability over the parameters it therefore suffices to condition on appropriate bounds for ∥S l (x)∥ 2 F and ∥S l (x)∥ 2 2 . These bounds are provided in Lemmas 34 and 35 in Appendices D.3 and D.4 respectively. With these two lemmas in place we can bound∥S l (x i )W T L ∥ 2 . Lemma 11. Let x ∈ S d0-1 , suppose L ≥ 3, d k ≥ d k+1 for all k ∈ [L -1] and d L-1 ≳ 2 L log L ϵ . Then, for any l ∈ [L -1], with probability at least 1 -ϵ over the network parameters ∥S l (x)W T L ∥ 2 ≍ 2 -L+l+1 L-1 k=l d k .By combining Lemma 11 with a union bound we arrive at the following corollary, relevant for the lower bound of (8).Corollary 12. Let x i ∈ S d0-1 for all i ∈ [n], L ≥ 3, d l ≥ d l+1 for all l ∈ [L -1] and d L-1 ≳ 2 L log nL ϵ .Then, for any l ∈ [L -1], with probability at least 1 -ϵ over the network parametersmin i∈[n] ∥[B 2 ] i,: ∥ 2 ≳ 2 -L L-1 k=2 d k .The first-layer feature Gram matrix F T 1 F 1 in the deep case is identically distributed to K 2 in the two-layer case; see (3) and the related definitions. Therefore we can apply Lemma 4 to lower bound the smallest eigenvalue of F T 1 F 1 . This, in combination with Corollary 12, yields the lower bound of Theorem 8. The upper bound follows by combining the bound on the feature norms provided by Lemma 10 with the bound on the backpropagation terms given in Lemma 11. A detailed proof of Theorem 8 is provided in Appendix D.6. 
conclusion: 
 Summary and implications. Quantitative bounds on the smallest eigenvalue of the NTK are a critical ingredient for many current analyses of network optimization. Prior works provide bounds which are only applicable for data drawn from particular distributions and for which the input dimension d 0 scales appropriately with the number of data samples n. This work plugs an important gap in the existing literature by providing bounds for arbitrary datasets on the sphere (including those drawn from any distribution on the sphere) in terms of a measure of distance between data points. Furthermore, these bounds are applicable for any d 0 , in particular even d 0 held constant with respect to n.Limitations. Our bounds currently only hold for the ReLU activation function. Another limitation, also present in prior work, is that our upper bound on the smallest eigenvalue of the NTK for deep networks in Theorem 8 does not capture the data separation. Finally, a mild limitation of this work is that we require the data to be normalized so as to lie on the sphere.Future work. The proof techniques developed here could be applied to analyze the NTK in the context of other homogeneous activation functions. One could potentially relax the homogeneity condition on the activation function, or the condition of unit norm data, by considering an integral transform on the space L 2 (R d , µ) rather than L 2 (S d-1 ), where µ denotes the standard Gaussian measure (since the weights are drawn from a Gaussian distribution). Beyond fully connected networks, conducting comparable analyses in the context of other architectures, e.g., CNNs, GNNs, or transformers, would be valuable future work. 
 
 Appendix: In order to bound the smallest eigenvalue of the finite-width NTK in terms of the expected, or infinite width NTK, we use the following matrix Chernoff bound variant. Lemma 13. Let R > 0, and letZ 1 , • • • , Z m ∈ R n×n be iid symmetric random matrices such that 0 ⪯ Z 1 ⪯ RI almost surely. Then P   λ min   1 m m j=1 Z j   ≤ 1 2 λ min (E[Z 1 ])   ≤ n exp - Cmλ min (E[Z 1 ]) R .Here C > 0 is a universal constant.Proof. By Theorem 1.1 of Tropp (2012) , for all δ > 0P   λ min   1 m m j=1 Z j   ≤ (1 -δ)λ min (E[Z 1 ])   = P   λ min   m j=1 Z j   ≤ (1 -δ)λ min   m j=1 E[Z j ]     ≤ n e -δ (1 -δ) 1-δ 1 R λmin( m j=1 E[Zj ]) = n e -δ (1 -δ) 1-δ m R λmin(E[Z1]) . Let δ = 12 and let C = 1 2 log e 2 > 0. Substituting into the above bound, we obtainP   λ min   1 m m j=1 Z j   ≤ 1 2 λ min (E[Z 1 ])   ≤ n 2 e m 2R λmin(E[Z1]) = n exp - Cmλ min (E[Z 1 ]) R .Some of our NTK bounds will depend on the operator norm of the input data matrix X, so it will be helpful to upper bound ∥X∥ with high probability.Lemma 14. Let ϵ > 0. Let X = [x 1 , • • • , x n ] ∈R d×n be a random matrix whose columns are independent and uniformly distributed on S d-1 . Then with probability at least 1 -ϵ,∥X∥ 2 ≲ 1 + n + log 1 ϵ d .Proof. We use a covering argument. Fix u ∈ S d-1 and v ∈ S n-1 . By Lemma 2.2 of Ball (1997) , for each i ∈ [n] and t ≥ 0,P(|⟨u, x i ⟩| ≥ t) ≤ 2 exp - dt 2 2 .In other words ∥⟨u,x i ⟩∥ ψ2 ≲ 1 √ d .Then by Hoeffding's inequality, for all t ≥ 0EQUATIONwhere Vershynin, 2018, Corollary 4.2.13) , we can take M ≤ 12 d . Similarly, let u 1 , • • • , u N be a 1 4 -covering of S n-1 with N ≤ 12 n . By applying a union bound to (9), we obtainC 1 > 0 is a constant. Let u 1 , • • • , u M be a 1 4 -covering of S d-1 . That is, u 1 , • • • , u M are a set of points in S d-1 such that for all u ∈ S d-1 , there exists j ∈ [M ] such that ∥u -u j ∥ ≤ 1 4 . Since the 1 4 -covering number of S d-1 is at most 12 d (seeP(|u T j Xv k | ≥ t for some j ∈ [M ], k ∈ [N ]) ≤ 2(12 d+n ) exp -C 1 dt 2 . Hence if t = (d + n) log 12 + log 2 ϵ d , then P(|u T j Xv k | ≤ t for all j ∈ [M ], k ∈ [N ]) ≥ 1 -ϵ.Let us condition on this event for the rest of the proof. Now suppose that u ∈ S d-1 and v ∈ S n-1 . By construction there exist j ∈[M ] and k ∈ [N ] such that ∥u -u j ∥ ≤ 1 4 and ∥v -v k ∥ ≤ 1 4 . Then |u T Xv| ≤ |u T j Xv k | + |(u -u j ) T Xv k | + |u T X(v -v k )| ≤ t + ∥u -u j ∥ • ∥v k ∥ • ∥X∥ + ∥u∥ • ∥X∥ • ∥v -v k ∥ ≤ t + 1 4 ∥X∥ + 1 4 ∥X∥ = t + 1 2 ∥X∥.Since this holds for all u ∈ S d-1 and v ∈ S n-1 , we obtain∥X∥ ≤ t + 1 2 ∥X∥.Rearranging yields∥X∥ 2 ≤ 4t 2 ≲ 1 + n + log 1 ϵ d .Here we review some preliminaries on spherical harmonics necessary for our main results. For further details we refer the reader to Efthimiou & Frye (2014) and Axler et al. (2013, Chapter 5) . Let L 2 (S d-1 ) denote the Hilbert space of real-valued, square-integrable functions on the sphere S d-1 , equipped with the inner product⟨g, h⟩ = S d-1 g(x)h(x) dS(x),where dS is the uniform probability measure on S d-1 . We let C(S d-1 ) ⊂ L 2 (S d-1 ) denote the subset of functions which are continuous. We say that a function g : R d → R is harmonic if it is twice continuously differentiable andd r=1 ∂ 2 g ∂ 2 x r (x) = 0for all x ∈ S d-1 . We say that a polynomial g :R d → R is homogeneous if there exists r ∈ Z ≥0 such that g(λx) = λ r g(x)for all λ ∈ R and x ∈ R d . Let H d r denote the vector space of degree r harmonic homogeneous polynomials on d variables, viewed as functions S d-1 → R. Each space H d r is a finite-dimensional vector space, withdim(H d r ) = r + d -1 d -1 - r + d -3 d -1 = 2r + d -2 r r + d -3 d -2 .For ν ≥ 0 and r ∈ N, we define the Gegenbauer polynomials C ν r byC ν r (t) = ⌊r/2⌋ k=0 (-1) k Γ(r -k + ν) Γ(ν)Γ(k + 1)Γ(r -2k + 1) (2t) r-2k .There exists an orthonormal basis ofH d r consisting of functions Y d r,s , 1 ≤ s ≤ dim(H d r ), known as spherical harmonics. The spherical harmonics in H d r satisfy the addition formuladim(H d r ) s=1 Y d r,s (x)Y d r,s (x ′ ) = dim(H d r )C (d-2)/2 r (⟨x, x ′ ⟩)Γ(r + 1)Γ(d -2) Γ(r + d -2) = (2r + d -2)C (d-2)/2 r (⟨x, x ′ ⟩) d -2 (10) for all x, x ′ ∈ S d-1 . In particular, from the identity C ν r (1) = Γ(2ν+r) Γ(2ν)Γ(r+1) it follows that dim(H d r ) s=1 |Y d r,s (x)| 2 = dim(H d r ).We can orthogonally decompose L 2 (S d-1 ) into a direct sum of the spaces of spherical harmonics:L 2 (S d-1 ) = ∞ r=1 H d r .That is, the spaces H d r are orthogonal and their linear span is dense in L 2 (S d-1 ). Lemma 15. Let δ > 0 and suppose that x, x ′ ∈ S d-1 satisfy ∥x -x ′ ∥, ∥x + x ′ ∥ ≥ δ. If R ∈ Z ≥0 , and β ∈ {0, 1}, then R r=0 dim(H d 2r+β ) s=1 Y d 2r+β,s (x)Y d 2r+β,s (x ′ ) ≲ ∥x -x ′ ∥ 2 2 -(d-2)/4 2R + β + d -1 d -1 1/2 . Proof. Let us define P (x, x ′ ) := R r=0 dim(H d 2r+β ) s=1 Y d 2r+β,s (x)Y d 2r+β,s (x ′ ).By the addition formula (10),EQUATIONIn order to bound the right hand side of the above equation, we will need a bound for the Gegenbauer polynomialsC (d-2)/2 2r+β. By Theorem 1 of Nevai et al. (1994) (see also equation 2.8 of Xie et al. 2013 ), for all ν ≥ 1 2 , r ≥ 0, and t ∈ [0, 1),(1 -t 2 ) ν C ν r (t) 2 ≤ 2e(2 + √ 2ν) π 2 1-2ν π Γ(ν) 2 Γ(r + 2ν) Γ(r + 1)(r + ν) ≲ νΓ(r + 2ν) 2 2ν (r + ν)Γ(ν) 2 Γ(r + 1).Rearranging the above expression yields|C ν r (t)| ≲ ν 1/2 Γ(r + 2ν) 1/2 2 ν (r + ν) 1/2 Γ(ν)Γ(r + 1) 1/2 (1 -t 2 ) ν/2 .We now substitute the above bound into (11):|P (x, x ′ )| ≲ R r=0 (r + d) d-2 2 1/2 Γ (2r + β + d -2) 1/2 d2 (d-2)/2 2r + β + d-2 2 1/2 Γ d-2 2 Γ(2r + β + 1) 1/2 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 ≲ 1 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 R r=0 r + d d 1/2 Γ(2r + β + d -2) 1/2 2 (d-2)/2 Γ d-2 2 Γ(2r + β + 1) 1/2 .The expression inside the sum is increasing as a function of r, so the above expression is bounded above byEQUATION)By Stirling's approximation,2 (d-2)/2 Γ d -2 2 ≍ 2 (d-2)/2 d -2 2 (d-3)/2 e -(d-2)/2 = (d -2) (d-3)/2 e -(d-2)/2 ≍ d -1/4 (d -2) (d-1.5)/2 e -(d-2)/2 ≍ d -1/4 Γ(d -1) 1/2 .Substituting this into (12) yields|P (x, x ′ )| ≤ 1 d 1/4 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 Γ(2R + β + d -1) 1/2 Γ(d -1) 1/2 Γ(2R + β + 1) 1/2 ≍ d 1/4 (R + d) 1/2 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 Γ(2R + β + d) 1/2 Γ(d)Γ(2R + β + 1) 1/2 = d 1/4 (R + d) 1/2 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 2R + β + d -1 d -1 1/2 ≲ 1 (1 -⟨x, x ′ ⟩ 2 ) (d-2)/4 2R + β + d -1 d -1 1/2 Since x, x ′ ∈ S d-1 , 1 -⟨x, x ′ ⟩ 2 = (1 + ⟨x, x ′ ⟩)(1 -⟨x, x ′ ⟩) = 1 4 ∥x + x ′ ∥ 2 ∥x -x ′ ∥ 2 ≳ 1 4 δ 4 .To conclude, we rewrite|P (x, x ′ )| ≲ δ 4 2 -(d-2)/4 2R + β + d -1 d -1 1/2.Let M(S d-1 ) denote the vector space of signed Radon measures on S d-1 . We denote the total variation of µ by |µ|. We have a natural inclusion L 2 (S d-1 ) ⊂ M(S d-1 ) by associating a function g to a signed measure µ defined byµ(E) = E g(x)dS(x).If µ ∈ M(S d-1 ) and g ∈ C(S d-1 ), we define the pairing ⟨µ, g⟩ by⟨µ, g⟩ = S d-1 g(x)dµ(x).This agrees with the usual definition of the inner product on L 2 (S d-1 ) when µ ∈ L 2 (S d-1 ).Fix ψ ∈ { √ dσ, σ}. If µ ∈ M(S d-1), we define its hemisphere transform (Rubin, 1999) T ψ µ : S d-1 → R by (T ψ µ)(ξ) = S d-1 ψ(⟨ξ, x⟩)dµ(x).As is the case with many integral transforms, a hemisphere transform increases the regularity of the functions it is applied to.Lemma 16. If µ ∈ M(S d-1 ), then T ψ µ ∈ L 2 (S d-1 ). If g ∈ L 2 (S d-1 ), then T ψ g ∈ C(S d-1 ).Proof. Suppose that µ ∈ M(S d-1 ). ThenS d-1 (T ψ µ)(ξ) 2 dS(ξ) = S d-1 S d-1 ψ(⟨ξ, x⟩)dµ(x) 2 dS(ξ) ≤ S d-1 S d-1 ψ(⟨ξ, x⟩)d|µ|(x) 2 dS(ξ) = S d-1 S d-1 S d-1 ψ(⟨ξ, x⟩)ψ(⟨ξ, x ′ ⟩)d|µ|(x)d|µ|(x ′ )dS(ξ) ≤ S d-1 S d-1 S d-1 d 2 d|µ|(x)d|µ|(x ′ )dS(ξ) = |µ|(S d-1 ) 2 d 2 < ∞, so T µ ∈ L 2 (S d-1 ).Now suppose that g ∈ L 2 (S d-1 ) and ψ = σ. Suppose that ξ, ξ ′ ∈ S d-1 , and observe thatdS({x ∈ S d-1 : ⟨x, ξ⟩ > 0, ⟨x, ξ ′ ⟩ ≤ 0}) = 1 2π arccos(⟨ξ, ξ ′ ⟩).Similarly,dS({x ∈ S d-1 : ⟨x, ξ⟩ ≤ 0, ⟨x, ξ ′ ⟩ > 0}) = 1 2π arccos(⟨ξ, ξ ′ ⟩), so dS({x ∈ S d-1 : σ(⟨x, ξ⟩) ̸ = σ(⟨x, ξ ′ ⟩)) = 1 π arccos(⟨ξ, ξ ′ ⟩).We apply this calculation to bound the distance between T ψ g(ξ) and T ψ g(ξ ′ ):|T ψ g(ξ) -T ψ g(ξ ′ )| = S d-1 σ(⟨x, ξ⟩)g(x)dS(x) - S d-1 σ(⟨x, ξ ′ ⟩)g(x)dS(x) ≤ S d-1 | σ(⟨x, ξ⟩) -σ(⟨x, ξ ′ ⟩)|g(x)dS(x) ≤ ∥g∥ L 2 S d-1 | σ(⟨x, ξ⟩) -σ(⟨x, ξ ′ ⟩)| 2 dS(x) 1/2 = ∥g∥ L 2 dS({x ∈ S d-1 : σ(⟨x, ξ⟩) ̸ = σ(⟨x, ξ ′ ⟩)) 1/2 = 1 π ∥g∥ L 2 arccos(⟨ξ, ξ ′ ⟩).Here the third line follows from Cauchy-Schwarz. As ξ → ξ ′ , arccos(⟨ξ, ξ ′ ⟩) → 0 and so |T ψ g(ξ) -T ψ g(ξ ′ )| → 0. Therefore, T ψ g ∈ C(S d-1 ).Finally suppose that g ∈ L 2 (S d-1 ) and ψ =√ dσ. For all ξ ∈ S d-1 , |dσ(⟨x, ξ⟩)g(x)| ≤ √ d|g(x)| ∈ L 1 (S d-1). So by the dominated convergence theorem, for all ξ ′ ∈ S d-1 ,lim ξ→ξ ′ T ψ g(ξ) = lim ξ→ξ ′ S d-1 √ dσ(⟨x, ξ⟩)g(x)dS(x) = S d-1 lim ξ→ξ ′ √ dσ(⟨x, ξ⟩)g(x)dS(x) = S d-1 √ dσ(⟨x, ξ ′ ⟩)g(x)dS(x) = T ψ g(ξ ′ ).Therefore T ψ g ∈ C(S d-1 ).By the above lemma, for any µ ∈ M(S d-1 ) and g ∈ L 2 (S d-1 ), the expressions ⟨T ψ µ, g⟩ and ⟨µ, T ψ g⟩ are well-defined and finite. In fact, they are equal to each other. Lemma 17. Suppose that µ ∈ M(S d-1 ) and g ∈ L 2 (S d-1 ). Then ⟨T ψ µ, g⟩ = ⟨µ, T ψ g⟩.Proof. We compute⟨T ψ µ, g⟩ = S d-1 (T ψ µ)(ξ)g(ξ)dS(ξ) = S d-1 S d-1 ψ(⟨x, ξ⟩)g(ξ)dµ(x)dS(ξ) = S d-1 S d-1 ψ(⟨x, ξ⟩)g(ξ)dS(ξ)dµ(x) = S d-1 T ψ g(x)dµ(x)= ⟨µ, T ψ g⟩. It remains to justify the change in order of integration in the third line. This follows from Fubini's theorem and the calculationS d-1 S d-1 |ψ(⟨x, ξ⟩)g(ξ)|dS(ξ)d|µ|(x) ≤ S d-1 S d-1 √ d|g(ξ)|dS(ξ)d|µ|(x) = S d-1 √ d∥g∥ L 1 d|µ|(x) = √ d∥g∥ L 1 |µ|(S d-1 ) < ∞,where the last line follows since g ∈ L 2 (S d-1 ) ⊂ L 1 (S d-1 ).In order to characterize how a hemisphere transform acts on L 2 (S d-1 ) and in particular on the spherical harmonics, we will use the Funk-Hecke formula (see Seeley, 1966) which states that a certain class of integral operators on S d-1 has an eigendecomposition of spherical harmonics. Lemma 18 (Funk-Hecke formula). Let ψ : [-1, 1] → R be a measurable function such that1 -1 |ψ(t)|(1 -t 2 ) (d-3)/2 dt < ∞.Then for all g ∈ H d rS d-1 ψ(⟨x, ξ⟩)g(x)dS(x) = c r,d g(ξ), where c r,d = Γ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 1 -1 ψ(t)C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt.We will now use the Funk-Hecke formula to compute the coefficients c r,d in the cases where ψ = √ dσ and ψ = σ. In the following calculations we will use the Legendre duplication formulaΓ(z)Γ z + 1 2 = 2 1-2z √ πΓ(2z)and Euler's reflection formulaΓ(1 -z)Γ(z) = π sin πz .Lemma 19. For all d ≥ 3 and r ≥ 0,1 0 C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = √ πΓ(d + r -2)Γ d-1 2 2Γ(d -2)Γ(r + 1)Γ 1 -r 2 Γ d+r 2 . and 1 0 tC (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = √ πΓ(d + r -2)Γ d-1 2 4Γ(d -2)Γ(r + 1)Γ 3-r 2 Γ d+r+1 2 .Proof. We apply the following identity (see Gradshteyn & Ryzhik, 2014, Equation 7.311.2):1 0 t r+2ρ C ν r (t)(1 -t 2 ) ν-1/2 dt = Γ(2ν + r)Γ(2ρ + r + 1)Γ ν + 1 2 Γ ρ + 1 2 2 r+1 Γ(2ν)Γ(2ρ + 1)r!Γ(r + ν + ρ + 1).By the Legendre duplication formula, we haveΓ ρ + 1 2 Γ(ρ + 1) = 2 -2ρ √ πΓ(2ρ + 1)so we can rewrite the above equation asEQUATION)Substituting ρ = -r/2 and ν = (d -2)/2 into (13) yields1 0 C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = √ πΓ(d + r -2)Γ d-1 2 2Γ(d -2)Γ 1 -r 2 Γ(r + 1)Γ d+r 2 ,which establishes the first identity of the claim.Substituting ρ = (1 -r)/2 and ν = (d -2)/2 into (13) yields1 0 C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = √ πΓ(d + r -2)Γ d-1 2 4Γ(d -2)Γ 3-r 2 Γ(r + 1)Γ d+r+1 2 ,which establishes the second identity of the claim.Lemma 20. Suppose that g ∈ H d r and d ≥ 3. Then for all r ≥ 0, T σ g = c r,d g, wherec r,d = Γ d 2 2Γ 1 -r 2 Γ r 2 + d 2 . Moreover, if 0 ≤ r ≤ R, then |c 2r+1,d | ≥ Γ d 2 Γ 2R+1 2 2πΓ d+2R+1 2 . Proof. Let g ∈ H d r . By Lemma 18, T σ g = c r,d g, where c r,d = Γ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 1 -1 σ(t)C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = Γ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 1 0 C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt.By Lemma 19, this is equal toΓ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 • √ πΓ(d + r -2)Γ d-1 2 2Γ(d -2)Γ(r + 1)Γ 1 -r 2 Γ d+r 2 = Γ d 2 2Γ 1 -r 2 Γ d+r 2 as claimed.Now we proceed with the second statement. We claim that whenever 0 ≤ r ≤ R,|c 2R+1,d | ≤ |c 2r+1,d |.We prove this by induction on R. For the base case R = r, the claim trivially holds. Now suppose that the claim holds for some R ≥ r. Then|c 2(R+1)+1,d | = Γ d 2 2Γ 1 -2R+3 2 Γ 2R+3 2 + d 2 = -2R+1 2 Γ d 2 2Γ 1 -2R+1 2 2R+1 2 + d 2 Γ 2R+1 2 + d 2 = |c 2R+1,d | 2R + 1 2R + 1 + d ≤ |c 2R+1,d | ≤ |c 2r+1,d |.2R+1,d | ≤ |c 2r+1,d | for all 0 ≤ r ≤ R. Now suppose that 0 ≤ r ≤ R. By Euler's reflection formula, c 2R+1,d = Γ d 2 2Γ 1 -2R+1 2 Γ 2R+1 2 + d 2 = Γ d 2 sin π 2R+1 2 Γ 2R+1 2 2πΓ 2R+1 2 + d 2 = Γ d 2 (-1) R Γ 2R+1 2 2πΓ 2R+1 2 + d 2 so |c 2r+1,d | ≥ |c 2R+1,d | = Γ d 2 Γ 2R+1 2 2πΓ d+2R+1 2 .Lemma 21. Suppose that g ∈ H d r and d ≥ 3. Then T √ dσ g = c r,d g, wherec r,d = √ dΓ d 2 4Γ 3-r 2 Γ d+r+1 2 . Moreover, if 0 ≤ r ≤ R, then |c 2r,d | ≥ √ dΓ d 2 Γ 2R-1 2 4πΓ d+2R+1 2 .Proof. The proof is analogous to that of Lemma 20. Let g ∈ H d r . By Lemma 18, T √ dσ g = c r,d g, wherec r,d = Γ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 1 -1 √ dσ(t)C (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt = √ dΓ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 1 0 tC (d-2)/2 r (t)(1 -t 2 ) (d-3)/2 dt.By Lemma 19, this is equal to√ dΓ(r + 1)Γ(d -2)Γ d 2 √ πΓ(d -2 + r)Γ d-1 2 • √ πΓ(d + r -2)Γ d-1 2 4Γ(d -2)Γ(r + 1)Γ 3-r 2 Γ d+r+1 2 = √ dΓ d 2 4Γ 3-r 2 Γ d+r+1 2 as claimed.We claim that whenever 0≤ r ≤ R, |c 2R,d | ≤ |c 2r,d |.We prove this by induction on R. For the base case R = r, the claim trivially holds. Now suppose that the claim holds for some R ≥ r. Then|c 2(R+1) | = √ dΓ d 2 4Γ 1-2R 2 Γ d+2R+3 2 = 1-2R 2 √ dΓ d 2 4Γ 1-2R 2 d+2R+1 2 Γ d+2R+1 2 = c 2R |2R -1| d + 2R + 1 ≤ c 2R .2R | ≤ |c 2r | for all 0 ≤ r ≤ R. Now suppose that 0 ≤ r ≤ R. By Euler's reflection formula, c 2R,d = √ dΓ d 2 4Γ 3-2R 2 Γ d+2R+1 2 = √ dΓ d 2 sin π 2R-1 2 Γ 2R-1 2 4πΓ d+2R+1 2 = (-1) R+1 √ dΓ d 2 Γ 2R-1 2 4πΓ d+2R+1 2 so |c 2r,d | ≥ |c 2R,d | = √ dΓ d 2 Γ 2R-1 2 4πΓ d+2R+1 2 .First we observe the connection between the smallest eigenvalue of the expected NTK when the weights are drawn uniformly over the sphere versus as Gaussian. Lemma 22. If X ∈ R d0×n , thenλ min E w∼N (0 d ,I d ) σ X T w σ w T X = d 0 λ min E u∼U (S d 0 -1 ) σ X T u σ u T X .Proof. Since the distribution of w is rotationally invariant, we can decompose w = αu, where α = ∥w∥, u is uniformly distributed on S d0-1 , and α and u are independent. Thenλ min E w∼N (0 d ,I d ) σ X T w σ w T X = λ min E σ X T w σ w T X = λ min E α 2 σ X T u σ u T X = λ min E α 2 E σ X T u σ u T X = d 0 λ min E σ X T u σ u T X .Lemma 22 is useful in that studying the expected NTK in the shallow setting for uniform weights here will prove more convenient than working directly with Gaussian weights.C.1 Proof of Lemma 3 Lemma 3. Suppose that x 1 , • • • , x n ∈ S d-1 . Let λ 1 = λ min E u∼U (S d-1 ) σ X T u σ u T X . If λ 1 > 0 and d 1 ≳ λ -1 1 ∥X∥ 2 log n ϵ , then with probability at least 1 -ϵ λ min (K 1 ) ≳ λ 1 .Proof. By the scale-invariance of σ,λ 1 = λ min E u∼N (0 d ,I d ) σ X T u σ u T X . For each i ∈ [n] and j ∈ [d 1 ], ∇ wj f (x i ) = 1 √ d 1 v j σ ⟨w T j , x i ⟩ x iand thereforeK 1 = 1 d 1 d1 j=1 Z j ,whereZ j = v 2 j σ X T w j σ w T j X ⊙ X T X . For each j ∈ [d 1 ], let ξ j ∈ {0, 1} be a random variable taking value 1 if |v j | ≤ 1 and taking value 0 otherwise. Since v j is a standard Gaussian there exists a universal constant C 1 > 0 with E[ξ j v j ] = C 1 for all j. We also define Z ′ j = ξ j Z j . Note that Z ′ j ⪰ 0, and by the inequalityλ max (A ⊙ B) ≤ max i [A] ii λ max (B), ∥Z ′ j ∥ = ξ j v 2 j σ X T w j σ (w j X) ⊙ X T X ≤ max i∈[n] ξ j v 2 j σ X T w j σ w T j X ii • X T X = max i∈[n] ξ j v 2 j σ w T j x i 2 • ∥X∥ 2 ≤ ∥X∥ 2 .Furthermore by the inequality λ min (A ⊙ B) ≥ min i [A] ii λ min (B),λ min E[Z ′ j ] = λ min E ξ j v 2 j σ X T w j σ w T j X ⊙ X T X ≥ λ min E ξ j v 2 j σ X T w j σ w T j X min i∈[n] X T X ii = λ min E ξ j v 2 j E σ X T w j σ w T j X min i∈[n] ∥x i ∥ 2 = C 1 λ min E σ X T w j σ w T j X = C 1 λ 1 .So by Lemma 13, for all t ≥ 0P   λ min   1 d 1 d1 j=1 Z ′ j   ≤ C 1 λ 1   ≤ P   λ min   1 d 1 d1 j=1 Z ′ j   ≤ E[Z ′ 1 ]   ≤ n exp - C 2 d 1 λ 1 ∥X∥ 2 where C 2 > 0 is a constant. Since Z j ⪰ Z ′ j for all j ∈ [d 1 ], if d 1 ≥ 1 C2λ1 ∥X∥ 2 log n ϵ , then P   λ min   1 d 1 d1 j=1 Z j   ≤ C 1 λ 1   ≤ n exp - C 2 d 1 λ 1 ∥X∥ 2 ≤ ϵ. C.2 Proof of Lemma 4 Lemma 23. Suppose that x 1 , • • • , x n ∈ S d0-1 . Let λ 2 = d 0 λ min E u∼U (S d 0 -1 ) σ(X T u)σ(u T X) .If λ 2 > 0 and d 1 ≳ n λ2 log n λ2 log n ϵ , then with probability at least 1 -ϵ, λ min (K 2 ) ≥ λ2 4 .Proof. Note that by Lemma 22,λ 2 = λ min E w∼N (0 d ,I d ) σ X T w σ w T X . For each i ∈ [n] and j ∈ [d 1 ], ∇ vj f (x i ) = 1 √ d 1 σ(w T j x i )and thereforeK 2 = 1 d 1 d1 j=1 Z j ,where Z j = σ X T w j σ w T j X . By Vershynin (2018, Theorem 6.3.2), for each j ∈[d 1 ] X T w j ψ2 ≲ X T w j -X T F ψ2 + ∥X T ∥ F ≲ ∥X T ∥ + ∥X T ∥ F ≲ ∥X T ∥ F = ∥X∥ F = √ n.So by Hoeffding's inequality, for all t ≥ 0P X T w j 2 ≥ t = P X T w j ≥ √ t ≤ 2 exp - C 1 t n (14)for some constant C 1 > 0. Let s = n C1 log 4n λ2C1 . For each j ∈ [d 1 ] let ξ j ∈ {0, 1} be a random variable taking value 1 if ∥X T w j ∥ 2 ≤ s and taking value 0 otherwise. Let Z ′ j = ξ j Z j . For each j ∈ [m], Z ′ j ⪰ 0, andZ ′ j = ξ j σ X T w j σ w T j X = ξ j σ X T w j 2 ≤ s.Moreover,E[Z j ] -E[Z ′ j ] = E (1 -ξ j )σ X T w j σ w T j X ≤ E (1 -ξ j ) σ X T w j σ w T j X = E (1 -ξ j ) σ X T w j 2 = 1 2 E (1 -ξ j ) X T w j 2 = 1 2 ∞ s P X T w j 2 ≥ t dt ≤ 2 ∞ s exp - C 1 t n dt = 2n C 1 exp - C 1 s n = λ 2 2 .Here we used (14) in line 6. By Weyl's inequality,λ min (E[Z ′ j ]) ≥ λ min (E[Z j ]) -E[Z j ] -E[Z ′ j ] = λ 2 - λ 2 2 = λ 2 2 .By Lemma 13,P   λ min   1 d 1 d1 j=1 Z ′ j   ≤ λ 2 4   ≤ P   λ min   1 m m j=1 Z ′ j   ≤ 1 2 λ min (E[Z ′ 1 ])   ≤ n exp - C 2 d 1 λ min (E[Z ′ 1 ]) s ≤ n exp -C 2 d 1 λ 2 2s .Since Z ′ j ⪯ Z j for all j, for d 1 ≥ 2s C2λ2 log n ϵ this impliesP   λ min   1 d 1 d1 j=1 Z j   ≤ λ 2 4   ≤ n exp - C 2 d 1 λ 2 2s ≤ ϵ.In other words,P λ min (K 2 ) ≥ λ 2 4 ≥ 1 -ϵ. C.3 Proof of Lemma 5 Lemma 5. Fix X ∈ R d×n and ψ ∈ { √ dσ, σ}. For all z ∈ R n , ⟨K ∞ ψ z, z⟩ = ∥T ψ µ z ∥ 2 . Moreover, λ min (K ∞ ψ ) = inf ∥z∥=1 ∥T ψ µ z ∥ 2 .Proof. We compute⟨K ∞ ψ z, z⟩ = E w∼U (S d-1 ) ψ w T X z 2 = S d-1 ψ w T X z 2 dS(w) = S d-1 n i=1 ψ(⟨w, x i ⟩)z i 2 dS(w) = S d-1 S d-1 ψ(⟨w, x⟩)dµ z (x) 2 dS(w) = S d-1 |T ψ µ z (w)| 2 dS(w) = ∥T ψ µ z ∥ 2which establishes the first part of the result. The second part of the result follows immediately by writingλ min (K ∞ ψ ) = inf ∥z∥=1 ⟨K ∞ ψ z, z⟩ = inf ∥z∥=1 ∥T ψ µ z ∥ 2 . C.4 Proof of Lemma 6 Lemma 6. Suppose x 1 , • • • , x n ∈ S d-1 are δ-separated. Suppose that β ∈ {0, 1} and that R ∈ Z ≥0 are such that N := R r=0 dim(H d 2r+β ) satisfies N ≥ C δ 4 2 -(d-2)/2where C > 0 is a universal constant. Let g 1 , • • • , g N be spherical harmonics which form an orthonormal basis ofR r=0 H d 2r+β . If D ∈ R N ×n is defined as D ai = g a (x i ) then σ min (D) ≥ N 2 .Proof. Note thatN = R r=0 2r + β + d -1 d -1 - 2r + β + d -3 d -1 = 2R + β + d -1 d -1 . Let us write D = [d 1 , • • • , d n ]. Fix i, k ∈ [n] with i ̸ = k.By the addition formula (10),∥d i ∥ 2 = N a=1 g a (x i ) 2 = R r=0 dim(H d 2r+β ) s=1 Y d r,s (x i ) 2 = R r=0 dim(H d 2r+β ) = N.By Lemma 15 and δ-separation, there exists a constant C > 0 such that|⟨d i , d k ⟩| = N a=1 g a (x i )g a (x k ) ≤ C δ 4 2 -(d-2)/4 2R + β + d -1 d -1 1/2 = CN 1/2 δ 4 2 -(d-2)/4 . Suppose that N ≥ 2C 2 δ 4 2 -(d-2)/2.Observe that σ min (D) is the square root of the minimum eigenvalue of D T D. By the Gershgorin circle theorem, the minimum eigenvalue of D T D is at leastmin i∈[n]   |(D T D) ii | - k̸ =i |D T D| ik   = min i∈[n]   ∥d i ∥ 2 - k̸ =i |⟨d i , d k ⟩|   ≥ N 2 .The result follows.Lemma 24. Let ϵ ∈ (0, 1) and let δ > 0. Suppose thatx 1 , • • • , x n ∈ S d-1 form a δ-separated dataset. Let R ∈ N be such that 2R + d -1 d -1 ≥ C δ 4 2 -(d-2)/2where C > 0 is a universal constant. Then∥T ψ µ z ∥ 2 ≳ (d + R) 1/2 d -1/2 R -3/2 if ψ = σ (d + R) -1/2 d 1/2 R -3/2 if ψ = √ dσ for all z ∈ R n with ∥z∥ ≤ 1.Proof. Let C be the same constant as in Lemma 6 and suppose that2R + d -1 d -1 ≥ C δ 4 2 -(d-2)/2 . Let β ∈ {0, 1} satisfy β = 1 when ψ = σ and β = 0 when ψ = dσ. Let N = R r=0 dim(H d 2r+β ). Note that N = R r=0 2r + d + β -1 d -1 - 2r + d + β -3 d -1 = 2R + d + β -1 d -1 ≥ 2R + d -1 d -1 ≥ C δ 4 2 -(d-2)/2 .Let g 1 , • • • , g N be spherical harmonics forming an orthonormal basis of R r=1 H d 2r-1 , and let B ∈ R N ×n be the matrix defined by B ai = g a (x i ). By Lemma 6, σ min (B) ≥ N 2 with probability at least 1 -ϵ. Since the functions g a are orthonormal,∥T ψ µ z ∥ 2 ≥ N a=1 |⟨T ψ µ z , g a ⟩| 2 .By Lemma 17 the above expression is equal toN a=1 |⟨µ z , T ψ g a ⟩| 2 = R r=0 dim(H d 2r+β ) s=1 |⟨µ z , T ψ Y 2r+β,s ⟩| 2 .By Lemmas 20 and 21,EQUATION)Hence∥T ψ µ z ∥ 2 ≥ R r=0 dim(H d 2r+β ) s=1 |c 2r+β,d | 2 |⟨µ z , Y 2r+β,s ⟩| 2 ≥ min 0≤r≤R |c 2r+β,d | 2 R r=0 dim(H d 2r+β ) s=1 |⟨µ z , Y 2r+β,s ⟩| 2 = min 0≤r≤R |c 2r+β,d | 2 N a=1 |⟨µ z , g a ⟩| 2 = min 0≤r≤R |c 2r+β,d | 2 N a=1 n i=1 z i g a (x i ) 2 = min 0≤r≤R |c 2r+β,d | 2 ∥Bz∥ 2 ≥ min 0≤r≤R |c 2r+β,d | 2 σ min (B) 2 ≥ N 2 min 0≤r≤R |c 2r+β,d | 2 .So by ( 15),EQUATION)We now separately analyze the cases where ψ = σ and ψ = dσ.Case 1: ψ = σ. In this case∥T ψ µ z ∥ 2 ≳ N Γ d 2 2 Γ 2R+1 2 2 Γ d+2R+1 2 2 = 2R + d d -1 • Γ d 2 2 Γ 2R+1 2 2 Γ d+2R+1 2 2 = Γ(2R + d + 1) Γ(d)Γ(2R + 2) • Γ d 2 2 Γ 2R+1 2 2 Γ d+2R+1 2 2 .Then by Stirling's approximation,∥T ψ µ z ∥ 2 ≳ (2R + d + 1) 2R+d+1/2 e -2R-d-1 d d-1/2 e -d (2R + 2) 2R+3/2 e -2R-2 • d 2 d-1 e -d 2R+1 2 2R e -2R-1 d+2R+1 2 d+2R e -d-2R-1 ≳ (d + 2R + 1) 1/2 d -1/2 2R + 1 2R + 2 2R (2R + 2) -3/2 ≳ (d + 2R + 1) 1/2 d -1/2 (2R + 2) -3/2 ≳ (d + R) 1/2 d -1/2 R -3/2 .Here the third inequality follows from the observations2R + 1 2R + 2 2R > 0 and lim R→∞ 2R + 1 2R + 2 2R = lim R→∞ 1 - 1 2R + 2 2R = e -1 .Case 2: ψ = √ dσ. In this case∥T ψ µ z ∥ 2 ≳ N dΓ d 2 2 Γ 2R-1 2 2 Γ d+2R+1 2 2 = 2R + d -1 d -1 • dΓ d 2 2 Γ 2R-1 2 2 Γ d+2R+1 2 2 = Γ(2R + d) Γ(d)Γ(2R + 1) • dΓ d 2 2 Γ 2R-1 2 2 Γ d+2R+1 2 2 .Then by Stirling's approximation,∥T ψ µ z ∥ 2 ≳ (2R + d) 2R+d-1/2 e -2R-d d d-1/2 e -d (2R + 1) 2R+1/2 e -2R-1 • d d 2 d-1 e -d 2R-1 2 2R-2 e -2R+1 d+2R+1 2 d+2R e -d-2R-1 ≳ (d + 2R) -1/2 d + 2R d + 2R + 1 d+2R d 1/2 (2R -1) -2 (2R + 1) 1/2 2R -1 2R + 1 2R ≳ (d + 2R) -1/2 d 1/2 R -3/2 d + 2R d + 2R + 1 d+2R 2R -1 2R + 1 2R = (d + 2R) -1/2 d 1/2 1 - 1 d + 2R + 1 d+2R 1 - 2 2R + 1 2R ≳ (d + R) -1/2 d 1/2 R -3/2 .Hence we have established the desired bound on ∥T ψ µ z ∥ 2 in all cases.Lemma 7. Let d ≥ 3 and suppose that x 1 , • • • , x n ∈ S d-1 are δ-separated. For all z ∈ R n with ∥z∥ ≤ 1 then ∥T ψ µ z ∥ 2 ≳      1 + d log(1/δ) log d -3 δ 2 if ψ = σ 1 + d log(1/δ) log d -3 δ 4 if ψ = √ dσ.Proof. We will consider multiple cases depending on the relative scaling of d and n. Let C > 0 be the same constant as in Lemma 24. First suppose that d≥ C δ 4 2 -(d-2)/2 . Let R = 1. Then 2R + d -1 d -1 = d ≥ C δ 4 2 (d-2)/2 . By Lemma 24, ∥T ψ µ z ∥ 2 ≳ 1 in this case. Next suppose that d ≤ C δ 4 2 -(d-2)/2 and √ d log d ≥ (8 log(1 + C) + 16d) log 2 δ . Let R = log(1 + C) + 2d log(2/δ) log d . Note that since d ≤ δ 4 2 -(d-2)/2, we havelog(1 + C) + 2d log(2/δ) log d ≥ 2d log(2/δ) d-2 2 log(2/δ 4 ) ≥ 1and thereforeR ≤ 2 log(1 + C) + 4d log(2/δ) log d ≤ √ d 4 .By definition,R ≥ log(1 + C) + 2d log(2/δ) log(d) so that 2R + d -1 d -1 ≥ 2R + d -1 2R 2R ≥ d 2R 2R = exp (2R(log(d) -log(2R)) ≥ exp 2R log(d) -log √ d = exp (R log d) ≥ exp(log(1 + C) + 2d log(2/δ)) ≥ C 2 δ 2d ≥ C 2 δ 4 (d-2)/2.Then by Lemma 24, the following bounds hold. If ψ = σ, then∥T ψ µ z ∥ 2 ≳ (d + R) 1/2 -1/2 R -3/2 ≳ R -3/2 ≳ 1 + d log(1/δ) log d -3/2 ≳ 1 + d log(1/δ) log d -3 δ 2 . If ψ = √ dσ, then ∥T ψ µ z ∥ 2 ≳ (d + R) -1/2 d 1/2 R -3/2 ≳ (d + √ d) -1/2 d 1/2 R -3/2 ≳ R -3/2 ≳ 1 + d log(2/δ) log d -3/2 ≳ 1 + log(n/ϵ) log d -3 δ 4 .Finally suppose that√ d log d ≤ (8 log(1 C) + 16d) log 2 δ and let R = (1 + 2C)d 2 δ 2(d-2)/(d-1) . Then R ≲ 1 + d 2 δ 2(d-2)/(d-1) ≤ (1 + d) 2 δ 2(d-2)/(d-1) ≤ 1 + √ d 2 2 δ 2(d-2)/(d-1) ≲ 1 + d log(1/δ) log(d) 2 2 δ 2(d-2)/(d-1) ≲ 1 + d log(1/δ) log(d) 2 δ -2 and 2R + d -1 d -1 ≥ 2R + d -1 d -1 d-1 ≥ R d d-1 ≥ 1 + 2C d d-1 2 δ 2/(d-2) . ≥ 2C(d -1) d 2 δ 2/(d-2) ≥ C 2 δ 2/(d-2).So by Lemma 24 the following bounds hold. If ψ = σ, then∥T ψ µ z ∥ 2 ≳ (d + R) 1/2 d -1/2 R -3/2 ≳ (1 + d) -1/2 R -1 ≳ 1 + d log(1/δ) log d -1 1 + d log(1/δ) log d -2 δ 2 = 1 + d log(1/δ) log d -3 δ 2 . If ψ = √ dσ, then ∥T ψ µ z ∥ 2 ≳ (d + R) -1/2 d 1/2 R -3/2 ≳ d + d 2 δ 2(d-2)/(d-1) -1/2 d 1/2 d 2 δ 2(d-2)/(d-1) -3/2 ≳ d -3/2 1 + 2 δ 2(d-2)/(d-1) -1/2 2 δ -3(d-2)/(d-1) ≳ (1 + d) -3/2 2 δ -4(d-2)/(d-1) ≳ 1 + d log(1/δ) log d δ 4 .Hence we have shown the desired bound on ∥T ψ µ z ∥ 2 in all cases.C.6 Upper bound on the minimum eigenvalue of the NTK Our strategy to upper bound λ min will be to prove that if two data points x, x ′ are close, then the Jacobian of the network does not separate points too much. We will need to find upper bounds for both ∥σ(W x) -σ(W x ′ )∥ and ∥ σ(W x) -σ(W x ′ )∥.Lemma 25. Let ϵ ∈ (0, 1). Suppose that x, x ′ ∈ S d-1 with ∥x -x ′ ∥ = δ. If d 1 = Ω log 1 ϵ , then with probability at least 1 -ϵ, ∥σ(W x) -σ(W x ′ )∥ ≲ δ d 1 .Proof. Note that ∥σ(W x)-σ(W x ′ )∥ 2 can be written a sum of iid subexponential random variables:∥σ(W x) -σ(W x ′ )∥ 2 = d1 j=1 (σ(⟨w j , x⟩) -σ(⟨w j , x ′ ⟩) 2 .Since the entries of each w j are iid standard Gaussian random variables and σ is 1-Lipschitz,∥(σ(⟨w j , x⟩) -σ(⟨w j , x ′ ⟩)) 2 ∥ ψ1 = ∥σ(⟨w j , x⟩) -σ(⟨w j , x ′ ⟩)∥ 2 ψ2 ≤ ∥⟨w j , x -x ′ ⟩∥ 2 ψ2 = ∥x -x ′ ∥ 2 = δ 2 . Moreover, E[(σ(⟨w j , x⟩) -σ(⟨w j , x ′ ⟩)) 2 ] ≤ E[|⟨w j , x -x ′ ⟩| 2 ] = ∥x -x ′ ∥ 2 = δ 2 .So by Bernstein's inequality, for all t ≥ 0P ∥σ(W x) -σ(W x ′ )∥ 2 ≥ δ 2 d 1 + t ≤ P ∥σ(W x) -σ(W x ′ )∥ 2 ≥ E[∥σ(W x) -σ(W x ′ )∥ 2 ] + t ≤ 2 exp -C min t 2 d 1 δ 4 , t δ 2 where C > 0 is a universal constant. Setting t = δ 2 d 1 with d 1 ≥ 1 C log 2 ϵ yields P(∥σ(W x) -σ(W x ′ )∥ 2 ≥ 2δ 2 d 1 ) ≤ 2 exp (-Cd 1 ) ≤ ϵ.This establishes the result.Lemma 26. Suppose that x, x ′ ∈ S d-1 . If w ∼ N (0, I d ), then P( σ(⟨w, x⟩) ̸ = σ(⟨w, x ′ ⟩)) ≍ ∥x -x ′ ∥. Proof. Recall that for x, x ′ ∈ S d-1 , P( σ(⟨w, x⟩) ̸ = σ(⟨w, x ′ ⟩)) = θ π ,where θ is the angle formed by x and x ′ ; that is, θ ∈ [0, π] withcos(θ) = ⟨x, x ′ ⟩ = 1 - 1 2 ∥x -x ′ ∥ 2 . By Taylor's theorem, 1 -cos(θ) = 1 2 θ 2 + O(θ 3 ), so 1 -cos(θ) ≍ θ 2 for θ ∈ [0, π]. This implies that θ 2 ≍ ∥x -x ′ ∥ 2 , so θ ≍ ∥x -x ′ ∥ and therefore P( σ(⟨w, x⟩) ̸ = σ(⟨w, x ′ ⟩)) ≍ ∥x -x ′ ∥. Lemma 27. Let ϵ ∈ (0, 1). Suppose that x, x ′ ∈ S d-1 with ∥x -x ′ ∥ δ. If d 1 = Ω 1 δ log 1 ϵ , then with probability at least 1 -ϵ, ∥v ⊙ σ(W x) -v ⊙ σ(W x)∥ ≲ δd 1 . Proof. Observe that ∥ σ(W x) -σ(W x ′ )∥ 2 = 4 d1 j=1 Z j = 4|S|, where Z j ∈ {0, 1} is equal to 1 if σ(⟨w j , x⟩) ̸ = σ(⟨w j , x ′ ⟩)and 0 otherwise, and S consists of the j ∈ [d 1 ] such that Z j = 1. The Z j are iid Bernoulli random variables with parameter p, where p ≍ δ by Lemma 26. By Chernoff's inequality (see Vershynin, 2018, Theorem 2.3.1) , for all t ≥ d 1 pP (|S| ≥ t) ≤ e -d1p ed 1 p t t Then setting t = ed 1 p with d 1 ≥ 1 p log 4 ϵ yields P (|S| ≥ ed 1 δ) ≤ P (|S| ≥ ed 1 p) ≤ e -d1p ≤ ϵ 4 .By the lower bound of Chernoff's inequality, for all t ≤ d 1 pP(|S| ≤ t) ≤ e -d1p ed 1 p t t .Then setting t = d1p e with d 1 ≥ 2 e-2 1 p log 4 ϵ yieldsP |S| ≤ d 1 p 2 ≤ exp - e -2 e d 1 p ≤ ϵ 4 .Therefore, with probability at least 1-ϵ 2 , d 1 δ e ≤ |S| ≤ ed 1 δ.Let us denote this event by ω. Observe that∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ 2 = 2 j∈S v 2 j and recall that v 2 j ∼ N (0, 1) for all j ∈ [d 1 ]. By Bernstein's inequality, for all t ≥ 0 P 1 2 ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ 2 ≥ |S| + t S ≤ 2 exp -C 1 min t 2 |S| , twhere C 1 > 0 is a universal constant. Setting t = |S| yieldsP ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≥ 2 |S| S ≤ 2 exp (-C 1 |S|) . Then P ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≤ 2 ed 1 ≥ P ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≤ 2 ed 1 δ, ω ≥ P ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≤ 2 |S|, ω ≥ E P ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≤ 2 |S| S 1 ω ≥ E [(1 -2 exp (-C 1 |S|)) 1 ω ] ≥ 1 -2 exp -C 1 d 1 δ e P(ω) ≥ 1 -2 exp -C 1 d 1 δ e 1 - ϵ 2 ,where we used that ω is measurable with respect to S in the fourth line. So if d 1 ≥ e C1δ log 4 ϵ , thenP ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≤ 2 ed 1 δ ≥ 1 - ϵ 2 1 - ϵ 2 ≥ 1 -ϵ. Lemma 28. Suppose that x ∈ S d-1 . If d 1 = Ω log 1 ϵ , then with probability at least 1 -ϵ, ∥v ⊙ σ(W x)∥ ≲ d 1 . Proof. Since σ(⟨w j , x⟩) ∈ {0, 1} for all j ∈ [d 1 ], ∥v ⊙ σ(W x)∥ 2 = d1 j=1 v 2 j σ(⟨w j , x⟩) ≤ d1 j=1 v 2 j .Since the entries v j are iid standard Gaussian random variables, Bernstein's inequality implies for all t ≥ 0P(∥v ⊙ σ(W x)∥ 2 ≥ d 1 + t) ≤ P   d1 j=1 v 2 j ≥ d 1 + t   ≤ 2 exp -C min t 2 d 1 , t . Setting t = d 1 with d 1 ≥ 1 C log 2 ϵ yields P(∥v ⊙ σ(W x)∥ 2 ≥ 2d 1 ) ≤ 2 exp(-Cd 1 ) ≤ ϵ.Now we prove our main lemma which we will use to relate the separation between data points to the NTK.Lemma 29. Let x, x ′ ∈ S d-1 with ∥x -x ′ ∥ ≤ δ ≤ 2. Let ϵ ∈ (0, 1). If d 1 = Ω 1 δ log 1 ϵ , then with probability at least 1 -ϵ, ∥∇ θ f (x) -∇ θ f (x ′ )∥ ≲ √ δ. Proof. By Lemma 27, if d 1 ≳ 1 δ log 1 ϵ , then with probability at least 1 -ϵ 4 , ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ ≲ δd 1 .Let us denote this event by ω 1 . By Lemma 28, if d 1 ≳ log 1 ϵ , then with probability at least 1 -ϵ 4 ,∥v ⊙ σ(W x)∥ ≲ d 1 .Let us denote this event by ω 2 . If both ω 1 and ω 2 occur, then∥∇ W1 f (x) -∇ W1 f (x ′ )∥ F = 1 √ d 1 ∥(v ⊙ σ(W x)) ⊗ x -(v ⊙ σ(W x ′ )) ⊗ x ′ ∥ F ≤ 1 √ d 1 ∥(v ⊙ σ(W x)) ⊗ x -(v ⊙ σ(W x)) ⊗ x ′ ∥ F + 1 √ d 1 ∥(v ⊙ σ(W x)) ⊗ x ′ -(v ⊙ σ(W x ′ )) ⊗ x ′ ∥ F ≤ 1 √ d 1 ∥v ⊙ σ(W x)∥ • ∥x -x ′ ∥ + 1 √ d 1 ∥v ⊙ σ(W x) -v ⊙ σ(W x ′ )∥ • ∥x ′ ∥ ≲ 1 √ d 1 d 1 δ + 1 √ d 1 δd 1 ≲ √ δ. By Lemma 25, if d l ≳ log 1 ϵ , then with probability at least 1 -ϵ 2 , ∥∇ W2 f (x) -∇ W2 f (x ′ )∥ = 1 √ d 1 ∥f 1 (x) -f 1 (x ′ )∥ ≲ δ.Let us denote this event by ω 3 . If ω 1 , ω 2 , and ω 3 all occur (which happens with probability at least 1 -ϵ), then∥∇ θ f (x) -∇ θ f (x ′ )∥ ≲ ∥∇ W1 f (x) -∇ W1 f (x ′ )∥ F + ∥∇ W2 f (x) -∇ W2 f (x ′ )∥ ≲ √ δ + δ ≲ √ δ. C.7 Proof of Theorem 1 Theorem 1. Let d ≥ 3, ϵ ∈ (0, 1), and δ, δ ′ ∈ (0, √ 2). Suppose that x 1 , • • • , x n ∈ S d-1 are δ-separated and min i̸ =k ∥x i -x k ∥ ≤ δ ′ . Define λ = 1 + d log(1/δ) log(d) -3 δ 2 . If d 1 ≳ ∥X∥ 2 λ log n ϵ , then with probability at least 1 -ϵ, λ ≲ λ min (K) ≲ δ ′ .Proof. First we prove the lower bound. Let λ 1 be as it is defined in Lemma 3. By Lemma 5,EQUATION)Then for such d 1 ,P(λ min (K 1 ) ≥ C 3 C 1 λ) ≥ 1 - ϵ 2 .This establishes the lower bound.Next we prove the upper bound. Let i, k∈ [n] be two indices with i ̸ = k such that ∥x i -x k ∥ ≤ δ ′ . If d 1 ≳ 1 λ log 1 ϵ ≳ 1 δ ′ log 1ϵ , then by Lemma 29 there exists C 4 > 0 such thatP(∥∇ θ f (x i ) -∇ θ f (x k )∥ 2 ≥ C 4 δ ′ ) ≥ 1 - ϵ 2 .Let us denote this event by ω. If ω occurs, thenλ min (K) ≲ (e i -e k ) T K(e i -e k ) = ∥∇ θ f (x) -∇ θ f (x k )∥ 2 ≲ δ ′ . with probability at least 1 -ϵ 2 , λ min (K) ≲ δ ′ .This establishes the upper bound for the minimum eigenvalue. The two-sided bound then immediately follows from a union bound.Our main bounds for the smallest eigenvalue of the NTK are stated in terms of the amount of separation between data points. To interpret our results in terms of probability distributions on the sphere, we will use a couple of lemmas which quantify the amount of separation for data which is uniformly distributed.For δ ∈ (0, 1/2) and x ∈ S d-1 , we define the spherical cap Cap(x, δ) = {y ∈ S d-1 : ∥y -x∥ ≤ δ}. and the double spherical cap DoubleCap(x, δ) = Cap(x, δ) ∪ Cap(-x, δ). By Lemma 2.3 of Ball (1997) ,EQUATIONWe can also obtain a corresponding upper bound on the volume of a spherical cap. Lemma 30. For x ∈ S d-1 and δ ∈ (0, 1/2),dS(Cap(x, δ)) ≤ 4 √ π(Cδ) d-1 d 2 .Here C > 0 is a universal constant.Proof. For ϕ ∈ [0, π], let S ϕ denote the set of all x ′ ∈ S d-1 such that the angle between x and x ′ is at most ϕ (that is, ⟨x, x ′ ⟩ ≥ cos(ϕ)). The measure of S ϕ is given by Li, 2010) . Here the numerator refers to the incomplete beta function and the denominator refers to the beta function. We can boundB(sin 2 (ϕ); (d -1)/2, 1/2) B((d -1)/2, 1/2) (see, e.g.B sin 2 (ϕ); d -1 2 , 1 2 = sin 2 (ϕ) 0 t (d-3)/2 (1 -t) -1/2 dt ≤ sin 2 (ϕ) 0 t (d-3)/2 dt = 2 d -1 sin(ϕ) d-1 . and B d -1 2 , 1 2 = Γ d-1 2 Γ 1 2 Γ d 2 ≥ Γ d-2 2 √ π Γ d 2 = 2 √ π d -2 .The above two bounds implyEQUATION) Now suppose that x ′ ∈ Cap(x, δ). Then ∥x-x ′ ∥ ≤ δ, so 1-⟨x, x ′ ⟩ ≤ 2δ 2 . Let ϕ = arccos(⟨x, x ′ ⟩)be the angle between x and x ′ . By Taylor's theorem,cos(ϕ) = 1 -ϕ 2 2 + O(ϕ 3 ), so 1 -cos(ϕ) ≍ ϕ 2 for ϕ ∈ [0, π]. Thus 2δ 2 ≥ 1 -⟨x, x ′ ⟩ = 1 -cos(ϕ) ≍ ϕ 2 .So the angle between x and x ′ is at most Cδ for some universal constant C > 0. It follows that Cap(x, δ) ⊆ S Cδ . Finally by ( 19),dS(Cap(x, δ)) ≤ 4 √ π(Cδ) d-1 d 2 .Since δ ≤ 1 2 , the sets Cap(x, δ) and Cap(-x, δ) are disjoint by the triangle inequality. Hence dS(DoubleCap(x, δ)) = 2Cap(x, δ)and in particular by Lemma 30EQUATION)for a constant C > 0.Lemma 31. Suppose that n ≥ 2 and ϵ ∈ (0, 1). If x 1 , • • • , x n ∈ S d-1 are independent and uniformly distributed on S d-1 , then with probability at least 1 -ϵ, the dataset is δ-separated withδ ≳ ϵ n 2 1/(d-1) . Proof. Let e = [1, 0, • • • , 0] T ∈ S d-1 . For each x ∈ S d-1, there exists an orthogonal matrix O x such that O x x = e. Note that for all x ∈ S d-1 and i ∈[n], O x x i d = x i . Let i, k ∈ [n] with i ̸ = k. Then for all δ ∈ (0, 1/2), P(∥x i -x k ∥ ≤ δ or ∥x i + x k ∥ ≤ δ) = E[P(∥x i -x k ∥ ≤ δ or ∥x i + x k ∥ ≤ δ | x k )] = E[P(∥O x k x i -O x k x k ∥ ≤ δ or ∥O x k x i + O x k x k ∥ ≤ δ | x k )] = E[P(∥O x k x i -e∥ ≤ δ or ∥O x k x i + e∥ ≤ δ | x k )] = E[P(∥x i -e∥ ≤ δ or ∥x i + e∥ ≤ δ | x k )] = P(∥x i -e∥ ≤ δ or ∥x i + e∥ ≤ δ).The expression on the final line is the measure of DoubleCap(e, δ), and by (20) is bounded above by4 √ π(Cδ) d-1 d 2 ,where C > 0 is a constant. SoP(∥x i -x k ∥ ≤ δ or ∥x i + x k ∥ ≤ δ for some i ̸ = k) ≤ i̸ =k P(∥x i -x k ∥ ≤ δ or ∥x i + x k ∥ ≤ δ) ≤ 4 √ πn 2 (Cδ) d-1 d 2 . Setting δ = min 1 4 , 1 C ϵd 2 4 √ πn 2 1/(d-1), we obtainP(∥x i -x k ∥ ≤ δ or ∥x i + x k ∥ ≤ δ for some i ̸ = k) ≤ ϵ.Therefore, for this value of δ, the dataset is δ-separated with probability at least 1 -ϵ. To conclude, note that1 C ϵd 2 4 √ πn 2 1/(d-1) ≳ ϵ n 2 1/(d-1) since lim d→∞ d 2 4 √ π 1/(d-1) = 1.Lemma 32. Suppose that n ≥ 2 and ϵ ∈ (0, 1).If x 1 , • • • , x n ∈ S d-1 are selected iid from U (S d-1), then with probability at least 1 -ϵ, there exist i, k ∈ [n] with i ̸ = k such that∥x i -x k ∥ ≲ log(1/ϵ) n 2 1/(d-1).Proof. Let e = [1, 0, • • • , 0] T ∈ S d-1 . For each x ∈ S d-1, there exists an orthogonal matrix O x such that O x x = e. Note that for all x ∈ S d-1 and i ∈[n], O x x i d = x i . Let i, k ∈ [n] with i ̸ = k. Then for all δ ∈ (0, 1/2), P(∥x i -x k ∥ ≤ δ) = E[P(∥x i -x k ∥ ≤ δ | x k )] = E[P(∥O x k x i -O x k x k ∥ ≤ δ | x k )] = E[P(∥O x k x i -e∥ ≤ δ | x k )] = E[P(∥x i -e∥ ≤ δ | x k )] = P(∥x i -e∥ ≤ δ).The expression on the final line is the measure of Cap(e, δ), and by Lemma 2.3 of Ball (1997) it is bounded below by 1 2 δ 2 d-1 . For each i ∈ [n], let ω i denote the event that ∥x j -x k ∥ > δ for all j, k ∈ [1, i] with j ̸ = k. Trivially P(ω 1 ) = 1. If ω i occurs for some i ∈ [1, n -1], then the sets Cap(x j , δ/2) for j ∈ [i] are disjoint. Indeed, if x ∈ Cap(x j , δ/2) ∩ Cap(x k , δ/2), then by the triangle inequality∥x j -x k ∥ ≤ ∥x -x j ∥ + ∥x -x k ∥ ≤ δ 2 + δ 2 = δwhich contradicts ω i . Now since these smaller spherical caps are disjoint, we can bounddS ∪ i j=1 {x ∈ S d-1 : ∥x -x j ∥ ≤ δ} ≥ dS ∪ i j=1 {x ∈ S d-1 : ∥x -x j ∥ ≤ δ/2} = dS ∪ i j=1 Cap(x j , δ/2) = i j=1 dS(Cap(x j , δ/2)) ≥ i j=1 1 2 δ 4 d-1 = i 2 δ 4 d-1.Since x i+1 is chosen independently from x 1 , • • • , x i , this impliesP(ω i+1 | ω i ) = P(∥x i+1 -x j ∥ > δ ∀j ∈ [i] | ω i ) ≤ 1 - i 2 δ 4 d-1.By repeatedly conditioning we obtainP(∥x j -x k ∥ > δ ∀j, k ∈ [n]) = P(ω n ) = P(ω 1 ) n i=2 P(ω i | ω 1 , • • • , ω i-1 ) = n i=2 P(ω i | ω i-1 ) ≤ n i=2 1 - i 2 δ 4 d-1 ≤ n i=2 exp - i 2 δ 4 d-1 ≤ exp - n 2 2 δ 4 d-1.Let us set δ = min 1 4 , 4 2 n 2 log 1 ϵ 1 d-1. The above bounds imply thatP(∥x j -x k ∥ > δ ∀j, k ∈ [n]) ≤ ϵ so with probability at least 1 -ϵ, there exist i, k ∈ [n] such that ∥x i -x k ∥ ≤ δ with δ ≲ n -2 log 1 ϵ 1/(d-1)which is what we needed to show.Corollary 2. Let d ≥ 3, n ≥ 2, ϵ ∈ (0, 1), x 1 , • • • , x n ∼ U (S d-1) be mutually iid. Defineλ = 1 + log(n/ϵ) log(d) -3 ϵ 2 n 4 1/(d-1).If d 1 ≳ 1 λ 1 + n+log(1/ϵ) dlog n ϵ , then with probability at least 1 -ϵ over the data and network parameters,λ ≲ λ min (K) ≲ log(1/ϵ) n 2 1/(d-1).Proof. By Lemma 14, with probability at least 1 -ϵ 4 ,∥X∥ 2 ≲ 1 + n + log 1 ϵ d .Let us denote this event by ω 1 . Let us defineδ := min i̸ =k min(∥x i -x k ∥, ∥x i + x k ∥) and δ ′ := min i̸ =k ∥x i -x k ∥.In particular, the dataset x 1 , • • • , x n is δ-separated. By Lemma 31, with probability at least 1 -ϵ 4 ,δ ≳ ϵ n 2 1/(d-1).Let us denote this event by ω 2 . By Lemma 32, with probability at least 1 -ϵ 4 ,δ ′ ≲ log(1/ϵ) n 2 1/(d-1).Let us denote this event by ω 3 . We condition on ω 1 , ω 2 , and ω 3 for the remainder of the proof. Defineλ ′ = 1 + d log(1/δ) log(d) -3 δ 2 and λ = 1 + log(n/ϵ) log(d) -3 ϵ 2 n 4 1/(d-1); note thatλ ′ ≳ 1 + d log (n 2 /ϵ) 1/(d-1) log(d) -3 ϵ n 2 2/(d-1) ≳ 1 + log(n/ϵ) log(d) -3 ϵ 2 n 4 1/(d-1) = λ.By Theorem 1, ifd 1 ≳ 1 λ 1 + n + log(1/ϵ) d log n ϵ ≳ 1 λ ′ ∥X∥ 2 log n ϵ ,then with probability at least 1 -ϵ 4 over the network weights,λ min (K) ≳ λ ′ ≳ λ and λ min (K) ≲ δ ′ ≲ log(1/ϵ) n 2 1/(d-1). This is exactly the bound that we needed to show. By taking a union bound over all of the favorable events, it follows that this event happens with probability at least 1 -ϵ. F l = [f l (x 1 ), • • • , f l (x n )].For l ∈ [L -1] and x ∈ R d we define the activation patterns Σ l (x) ∈ {0, 1} d l ×d l to be the diagonal matricesΣ l (x) = diag( σ(W l f l-1 (x))).Lemma 9 provides a useful decomposition of the NTK.Lemma 9. Let x 1 , • • • , x n ∈ R d be nonzero.There exists an open set U ⊂ P of full Lebesgue measure such that f (x i ; •) is continuously differentiable on U for all i ∈ [n]. Moreover, for all θ ∈ U the NTK Gram matrix K defined in (1) with network function (7) satisfiesL-1 l=1 d l 2 K= L-1 l=0 (F T l F l ) ⊙ (B l+1 B T l+1 ),where the ith row of B l ∈ R n×n l is defined as[B l ] i,: = Σ l (x i ) L-1 k=l+1 W T k Σ k (x i ) W T L , l ∈ [L -1], 1 n , l = L.Proof. For any i ∈ [n], observe that f (x i , •) is a PAP function (Lee et al., 2020b, Definition 5 ) and therefore f (x i , •) is differentiable almost everywhere (Lee et al., 2020b, Proposition 4) . As the union of n null sets is also a null set, we conclude that there exists an open set U of full measure such that for all i ∈ [n] then f (x i , θ) is differentiable for any θ ∈ U .Let ∂f ∂θ denote the true derivative of f with respect to θ when it exists and be the minimum norm sub-gradient otherwise. Using (Lee et al., 2020b, Corollary 13) thenL-1 l=1 d l 2 K a.e. = ∂F L (θ) ∂θ T ∂F L (θ) ∂θ = L l=1 ∂F L (θ) ∂W l T ∂F L (θ) ∂W l ,where ∂F L (θ) ∂W l ∈ R d l d l-1 ×n . By inspection, to prove the result claimed it therefore suffices to show for any l ∈ [L], θ ∈ U and i, j ∈ [n] thatEQUATIONFirst observeEQUATIONAs a result,∂f L (x; θ) ∂θ l = W L L-l+1 k=1 Σ L-k (x)W L-k ∂f l (x; θ) ∂W l = W L L-l+1 k=1 Σ L-k (x)W L-k (Σ l (x) ⊗ f l-1 (x; θ))where the first equality arises from iterating ( 22) and the second by applying (23). Proceeding, ∂f L (x i ) ∂θ l , ∂f L (x j ) ∂θ l = f l-1 (x i ) T f l-1 (x j ) Σ l (x i ) L-1 k=l+1 W T k Σ k (x i ) W T L T Σ l (x j ) L-1 k=l+1 W T k Σ k (x j ) W T L = f l-1 (x i ) T f l-1 (x j ) [B l ] T i,: [B l ] j,: as claimed.∈ (0, 1) if m ≳ δ -2 log(1/ϵ) then P (1 -δ) m 2 ∥z∥ 2 ≤ ∥y∥ 2 ≤ (1 + δ) m 2 ∥z∥ 2 ≥ 1 -ϵ. Proof. For i ∈ [m] define Z i = w T i z ∥z∥ , then Z i ∼ N (0, 1) are mutually iid. Let B i = 1(Z i > 0),note by symmetry B i ∼ Ber(1/2), furthermore these random variables for i ∈ [n] are also mutually iid with respect to one another. Asy i = ∥z∥B i Z i then ∥y∥ 2 2 = ∥z∥ 2 m i=1 B i Z 2 i .For convenience let y ′ = y/∥z∥and define S = {i ∈ [n] :B i = 1}, then ∥y ′ ∥ 2 = i∈S Z 2 i ∼ χ 2 (|S|).From (Laurent & Massart, 2000 , Lemma 1) we have for any t > 0P | ∥y ′ ∥ 2 -|S| | ≥ 2 |S|t ≤ 2 exp(-t).For δ 1 ∈ (0, 1) let t = |S|δ 2 1 4 , thenP (1 -δ 1 )|S| ≤ ∥y ′ ∥ 2 ≤ (1 + δ 1 )|S| ≥ 1 -2 exp - |S|δ 2 1 4 . Observe |S| = m i=1 B i ∼ Bin(m, 1/2).With δ 2 ∈ (0, 1) then applying Hoeffding's inequality we haveP (1 -δ 2 ) m 2 ≤ m i=1 B i ≤ (1 + δ 2 ) m 2 ≥ 1 -2 exp - δ 2 2 m 2 .Let ω denote the event that(1 -δ 2 ) m 2 ≤ |S| ≤ (1 + δ 2 ) m 2 . If m ≥ 16 δ 2 1 δ 2 2 (1-δ2) log(4/ϵ) then P (1 -δ 1 )(1 -δ 2 ) m 2 ≤ ∥y ′ ∥ 2 ≤ (1 + δ 1 )(1 + δ 2 ) m 2 ≥ P (1 -δ 1 )(1 -δ 2 ) m 2 ≤ ∥y ′ ∥ 2 ≤ (1 + δ 1 )(1 + δ 2 ) m 2 | ω P(ω) ≥ P (1 -δ 1 )|S| ≤ ∥y ′ ∥ 2 ≤ (1 + δ 1 )|S| | ω P(ω) ≥ 1 -2 exp - (1 -δ 2 )δ 2 1 m 8 1 -2 exp - δ 2 2 m 2 ≥ 1 - ϵ 2 1 - ϵ 2 ≥ 1 -ϵ. For some δ ∈ (0, 1) let δ 2 = δ 1 = δ/3, then if m ≥ 1944δ -2 log(4/ϵ) we have P (1 -δ) m 2 ≤ ∥y ′ ∥ 2 ≤ (1 + δ) m 2 ≥ 1 -ϵfrom which the result claimed follows.Lemma 10. Let x ∈ S d0-1 , L ≥ 2 and l ∈EQUATIONholds with probability at least 1 -ϵ over the network parameters.Proof. For k ∈ [l] let ω k denote the event that the inequalityEQUATIONholds. We proceed by induction to establish that P(ω k ) ≥ (1 -ϵ l ) k for all k ∈ [l]. For the base case note that f 1 (x) = σ(W 1 x) and ∥x∥ 2 = 1. Applying Lemma 33 with δ = 1 l , if d 1 ≳ l 2 log(l/ϵ) then P(ω 1 ) ≥ 1 -ϵ l . Now suppose for k ∈ [l -1] that P(ω k ) ≥ (1 -ϵ l ) k . Note P(ω k+1 ) ≥ P(ω k+1 | ω k )P(ω k ) ≥ P(ω k+1 | ω k )(1 -ϵ l ) k Recall f k+1 (x) = σ(W 1 f k (x)). Conditioned on ω k , then again applying Lemma 33 with δ = 1 l and as d k+1 ≳ l 2 log(l/ϵ) we haveEQUATIONholds with probability at least 1 -ϵ.Lemma 34. Let x ∈ S d0-1 , L ≥ 2 and assume d k ≳ L 2 log L ϵ for all k ∈ [L -1]. For any l ∈ [L -1] with probability at least 1 -ϵ over the network parameters the following holds,∥S l (x)∥ 2 F ≍ 2 -L+l+1 L-1 k=l d k .Proof. In what follows for convenience we define an empty product of scalars or matrices as the scalar one. Let K ∈ {L -1}, l ∈ [K], and for some arbitrary x ∈ S d0-1 defineS l,K = Σ l (x) K k=l+1 W T k Σ k (x).Let ω l,K denote the eventEQUATIONIt suffices to lower bound the probability of the event ω l,L-1 . Let F K denote the σ-algebra generated by W 1 , • • • , W K and note that S l,K ∈ F K . Let γ l denote the event that f l (x) ̸ = 0, thenP(ω l,L-1 ) ≥ P(ω l,L-1 | ω l,L-2 )P(ω l,L-2 ) ≥ P(ω l,L-1 | ω l,L-2 )P(ω l,L-2 | ω l,L-3 )P(ω l,L-3 ) ≥ L-2 h=l P(ω l,h+1 | ω l,h ) P(ω l,l | γ l )P(γ l ).Fixing ϵ ∈ (0, 1), our goal is to show each term in this product is at least (1 -ϵ L ): indeed, if this is true thenP(ω l,L-1 ) ≥ 1 - ϵ L L-l ≥ 1 -ϵand our task is complete. To this end, first observe that as d k ≳ L 2 log(L/ϵ) for all k ∈ [L -1], then P(γ l ) ≥ 1 -ϵ L by Lemma 10. Proceeding to the termP(ω l,l | γ l ), recall [Σ l (x)] jj = 1([W l f l-1 (x)] j > 0). By symmetry the diagonal entries of Σ l (x) are mutually iid Bernoulli random variables with parameter 1 2 . Therefore, using Hoeffding's inequality for all t ≥ 0P ∥Σ l (x)∥ 2 F - d l 2 ≥ t γ l ≤ 2 exp - t 2 d l . Let t = d l , if d l ≥ log 2L ϵ then with K ≥ 1, L ≥ 2 it follows that P(ω l,l | γ l ) = P 1 2 1 - 1 L K ≤ ∥Σ l (x)∥ 2 F 2 d l ≤ 2 1 + 1 L K γ l ≥ P 1 2 ≤ ∥Σ l (x)∥ 2 F 2 d l ≤ 3 2 γ l ≥ 1 -P ∥Σ l (x)∥ 2 F - d l 2 ≥ d l 4 γ l ≥ 1 - ϵ L .We now proceed to analyzeP(ω l,h+1 | ω l,h ) for h ∈ [l, K -1]. Note if ω l,h is true then ∥S l,h ∥ 2 F > 0. By definition this implies ∥Σ l (x)∥ 2 F > 0, however, if f h (x) = 0 then ∥Σ l (x)∥ 2 F = 0.Therefore ω l,h being true implies f h (x) ̸ = 0. For convenience in what follows we denote the jth column of W h+1 as w j . By definitionS l,h+1 = S l,h W T h+1 Σ h+1 (x), therefore, E[∥S l,h+1 ∥ 2 F | F h ] = E[∥S l,h W T h+1 Σ h+1 (x)∥ 2 F | F h ] = E   d h+1 j=1 ∥S l,h w j ∥ 2 σ(⟨w j , f h (x)⟩) F h   .As highlighted already, if we condition on ω l,h then f h (x) ̸ = 0 and therefore the random variables ( σ(⟨w j , f h (x)⟩)) j∈d h+1 are mutually iid Bernoulli random variables with parameter 1 2 . Again by symmetry σ(⟨w j , f h (x)⟩) is independent of ∥S l,h w j ∥ 2 . Therefore conditioned on ω l,hd h+1 j=1 E[∥S l,h w j ∥ 2 | F d h+1 ]E[ σ(⟨w j , f h (x)⟩) | F h ] = 1 2 d h+1 j=1 E[∥S l,h w j ∥ 2 | F h ] = 1 2 d h+1 j=1 ∥S l,h ∥ 2 F = d h+1 2 ∥S l,h ∥ 2 F .Moreover, under the same conditioning∥S l,h w j ∥ 2 σ(⟨w j , f h (x)⟩) ψ1 ≤ ∥∥S l,h w j ∥ 2 ∥ ψ1 = ∥∥S l,h w j ∥∥ 2 ψ2 ≲ ∥S l,h ∥ 2 Fwhere the last line follows from Theorem 6.3.2 of Vershynin (2018) . As a result, conditioned on ω l,h then using Bernstein's inequality (Vershynin, 2018, Theorem 2.8.1) there exists an absolute constant c such that for all t ≥ 0P ∥S l,h+1 ∥ 2 F - d h+1 2 ∥S l,h ∥ 2 F ≥ t F h ≤ 2 exp -c min t 2 d h+1 ∥S l,h ∥ 4 F , t ∥S l,h ∥ 2 F . If d h+1 ≥ 4L 2 c log 2L ϵ and t = d h+1 ∥S l,h ∥ 2 F 2Lthen conditioning on ω l,h we obtainP ∥S l,h+1 ∥ 2 F - d K 2 ∥S l,h ∥ 2 F ≥ d h+1 2L ∥S l,h ∥ 2 F F h ≤ ϵ L .As a result, for any h ∈ [l, K -1] we have P(ω l,h+1 | ω l,h ) ≥ 1 -ϵ L from which the result claimed follows.35 Lemma 35. Let x ∈ S d0-1 , L ≥ 3 and assume d k ≥ d k+1 and d k ≳ log 1 ϵ for all k ∈ [L -1].For any l ∈ [L -1] with probability at least 1 -ϵ over the network parameters the following holds,∥S l (x)∥ 2 ≲ L-2 k=l d k .Proof. By Theorem 4.4.5 of Vershynin (2018) , for any k ∈ [L -1] and all t ≥ 0P ∥W k ∥ ≤ C( d k-1 + d k + t) ≥ 1 -2e -t 2 . As d k-1 ≥ d k ≥ log 2L ϵ , then setting t = log 2 ϵ yields P ∥W k ∥ ≤ 3C 1 d k-1 ≥ P ∥W k ∥ ≤ C( d k-1 + d k + t) ≥ 1 - ϵ L .Using a union bound it follows thatP ∥W k ∥ ≤ 3C 1 max{ d l-1 , d l } ∀k ∈ [L -1] ≥ 1 -ϵ.Note that ∥Σ k (x)∥ ≤ 1 for all k ∈ [L -1], therefore conditional on the above event we have∥S l (x)∥ = Σ l (x) L-1 k=l+1 W T k Σ k (x) ≤ ∥Σ l (x)∥ L-1 k=l+1 ∥W k ∥∥Σ k (x)∥ ≤ L-1 k=l+1 ∥W k ∥ ≲ L-2 k=l d k .To conclude we square both sides. Proof. Let x ∈ S d0-1 be arbitrary and recall S l (x) = Σ l (x)L-1 k=l+1 W T k Σ k (x) . Also recall that W T L ∈ R d L-1 is distributed as W T L ∼ N (0 d L-1 , I d L 1 ). Therefore by Vershynin (2018, Theorem 6.3.2) for any A ∈ R d2×d L-1 and t ≥ 0P(|∥AW T L ∥ 2 -∥A∥ F | ≥ t) ≤ 2 exp - Ct 2 ∥A∥ 2 2for some constant C > 0. As a result, with t = 1 2 ∥A∥ 2 F then for some constant C > 0P 1 4 ∥A∥ 2 F ≤ ∥AW T L ∥ 2 2 ≤ 3 4 ∥A∥ 2 F ≥ 1 -exp -C ∥A∥ 2 F ∥A∥ 2 2 .Therefore, in order to lower bound ∥S l (x)W T L ∥ 2 2 with high probability it suffices to condition on a suitable upper bound for ∥S L-1 (x)∥ 2 2 and a suitable lower bound for ∥S L-1 (x)∥ 2 F . Let ω denote the event that both where the upper bound holds for any i ∈ [n]. We start by analyzing the lower bound. Observe that F 1 F T 1 = σ(W 1 X) T σ(W 1 X) has the same distribution as d 1 K 2 in the shallow setting; see (3). Let λ 2 be defined as in Lemma 4:λ 2 = d 0 λ min E u∼U (S d 0 -1 ) σ(u T X) T σ(u T X) = λ min K ∞ √ d0σ .As the dataset x 1 , x 2 , • • • , x n ∈ S d0-1 is δ-separated then by Lemma 7 holds with probability at least 1 -ϵ 2L . Again using a union bound now over the layers, it follows that2 L-1 L-1 l=1 1 d l L-1 l=0 ∥f l (x i )∥ 2 ∥[B l+1 ] i,: ∥ 2 ≲ L2 L-1 L-1 l=1 1 d l 2 -L+1 L-1 l=1 d l = L (25)with probability at least 1 -ϵ 2 . As a result, using a final union bound we conclude both the upper and lower bounds hold with probability at least 1 -ϵ.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: None of the potential harms mentioned apply directly to our work. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work is primary theoretical and does not have direct societal impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 


Decision: A fine work deriving bounds for the smallest eigenvalue of the NTK that hold under relaxed distributional assumptions. The reviewers have unanimously voted for acceptance.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: 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?
limitations: limitations: -
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Please refer to weaknesses
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: The major weaknesses of the paper are addressed by the authors and provide avenue for future research.
questions: questions: None
limitations: limitations: The authors have addressed the limitations of the work. This is a theoretical paper so the broader societal impact is negligible.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: The main concerns were mentioned in the "weaknesses" part.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: This paper is theoretical and limitations are stated clearly in the paragraphs (lines 317-320).

Comments: title: Response
comment: 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.
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
Thank you for the rebuttal. My concerns have been well addressed, and I would like to keep my positive score of this paper.
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)
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.