Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension
Authors: Kedar Karhadkar
Michael Murray
Guido Montufar
Venue: NeurIPS 2024 poster (2024)
Keywords: neural tangent kernel
initialization
minimum eigenvalue
smallest eigenvalue
low-dimensional
hemisphere transform
spherical harmonics
separated
Primary area: learning_theory
TL;DR: We bound the smallest eigenvalue of the NTK without distributional assumptions on the data.

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.

Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension
Kedar Karhadkar', Michael Murray', Guido Montúfar
DDepartment of Mathematics, UCLA
2 Department of Statistics & Data Science, UCLA
Max Planck Institute MiS
Abstract
Bounds on the smallest eigenvalue of the neural tangent kernel (NTK) are key ingredient in the analysis of neural network optimization and memorization. How- ever, existing results require distributional assumptions the data and are limited to a high-dimensional setting, where the input dimension dg scales at least log- arithmically in the number of samples In this work remove both of these requirements and instead provide bounds in terms a measure of distance between data points: notably these bounds hold with high probability even when do is held constant versus n. We prove our results through a novel application of the hemisphere transform.
Introduction
A popular approach for studying the optimization dynamics of neural networks is analyzing the neural tangent kernel (NTK), which corresponds 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 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. [019a]] Montanari Zhhng 2022) ) and data memorization capacity (Montanari Zhong 2022; Nguyen et al., [002]]
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 & Liang 2018 Du al., [019a] Allen-Zhu et al.) (019) required unrealistic conditions on the width of the layers, subsequent and substantive efforts have reduced the level of overparametrization
LLi
required ensure that the NTK is well conditioned at initialization (Zou & Gu 2019 Oymak &
Soltanolkotabi] 2020). In particular, Nguyen (202)) Nguyen et al. (2021): Banerjee et al. (2023) showed that layer width scaling linearly in the number of training samples suffices to bound the smallest eigenvalue and Montanari & Zhong (022);; Bombari et al. (2022) obtained results for networks with sub-linear layer width and the minimum possible number of parameters 21(n) up to logarithmic factors. However,
as discussed in Section [ the bounds provided in prior works require that the data is drawn from a distribution satisfying Lipschitz concentration property, and only hold with high probability if the input dimension do 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 training samples n increases and as such there a gap in our understanding of cases where the data is sampled from 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 IRdd x P - R. where P is an inner product space. To be clear, (ax; 0) denotes the output of the network for given input æ E Rdd and parameter choice O E P. For brevity we occasionally write f(x) in place of f(;; Q) if the context is clear. We use denote the size of the training sample. dg the dimension of the input features, the network depth, di the width of the (th layer and a: IR- + - the ReLU activation function. Given n input data points æ1, .... In
Red we write X [1,.. ... Fnd Ro and define F : P + R" to be the evaluation of the network on these n data points as function of the parameter O,
F(O) [f 0), ((xx;00)²
We define the neural tangent kernel (NTK) of F
K(0) = (V (0) (V)F(0)) E R"**,
(I)
where the gradient V and adjoint are taken with respect the inner product on P and the Euclidean inner product on R", More explicitly [K) (o, 0), (af 0)). For convenience we write K in place of K (0). We are concerned with the minimum eigenvalue Aunin (K), which depends both on the input data X and the parameter O. We say the dataset ",, En is 6-separated for
5 E (0, 22] if min min([|2; zxll. x + x II) 2 6, which is measure of distance in direction.
Main contributions. Our results are for data that lies on a sphere and is 6-separated for some (0, v2j. 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 dg to scale with the number of samples n.
In Theorem Te consider shallow ReLU networks with input dimension dg and hidden width dj and prove that if dj = S2[[ 2 |2=0 d))-2) then with high probability Amin K) = ((d 8²).
Furthermore, defining 8' min ||,r, - æx Il. we have Amin (nin(() = O88).
In Thcorem 8 we illustrate how our results for shallow networks
be extended to cover depth-L networks. In particular, if the layer widths satisfy a pyramidal condition, meaning
di 2 d(+1 for E (1,.... L - 1}. di-1 2 2- log(mL/e) and d1 = 2(nd865 -1), 1), then Amin (K) = (dd 384) and Amin (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 5-separation with high probability in terms of do and n. For example, for shallow networks with data drawn uniformly from a sphere, in Corollary 2 we show that if dod; = 52(n 144/(do-1)) then with high probability Xmin
Ô (n 2/ (1) and Amin (K) = Q (n 4/(do-1)). Morcover, this bound is tight up to logarithmic factors for de = (2(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 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, nn denote the set of the first n positive integers. If a: Rdd then let [ar]; denote the ith entry of æ. If f and g are real-valued functions, we write f S g or f = Ogg) when there exists an absolute constant C' such that fx) Cg(x) for all x. Similarly, we write f 2 g or f 2(g) when there exists a constant e such that f(x) 2 cg(x) for all r. We write f x when f S g and f Z both hold. The notation Ω hides logarithmic factors. Logarithms are generally considered to be in base though in most settings the particular choice of base can be absorbed by constant.
2 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 selnite-widthh limit the NTK converges in probability to deterministic kernel. Of particular interest is the observation that in the infinite-width setting the network behaves like linear model (Lee et al. 2019). Further, if 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 result, assuming the latter is positive, global convergence guarantees for gradient descent can be obtained (Du et al., 2019a Allen- Zhu et al. 2019 Zou & Gu 2019, Lee
cet al. 2019: & Soltanolkotabi, 2020 Zou et al. 2020 Nguyen & Mondelli 2020 Nguyen
202T Banerjee et al. 2003).. 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 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 [202]] Murray et al.
2023), which has implications on the dynamicss of the empirical risk (Arora et al.] [201bb] Velikanov
& Yarotsky, 202T) well as the generalization error (Cao et al. [002]] Basri al. 20200] Cui et al.
2in et al.] [202]] Bowman & Montúfar (022). 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 2020
Prior work on the smallest eigenvalue of the NTK. Many of the prior works discussed so far assume or prove that Amin (K) is positive, but do not provide 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 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- con-vucuous is necessary that d, {2(d1n). while Montanari & Zhong Theorem 3.2) requires, as per their Assumption 3.1, that dg = D(Vn).
(002
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 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 Amin (K) = 222 )do) (or 12 (o)) with normalized data), where μe, (or) denotes the rth Hermite coefficient of a with any even integer r 1 2. However, in their result the bound holds with high probability only if do 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, meaning di = O(d,1) for all 1 E [L - 1]. (d.-iddi-- scales linearly in n (ignoring logarithmic factors), and there exists y > such that n² = O(d.-1). Under these conditions they show that Amin (K) -ddz-1d with high probability as both d 1 and n grow. This result illustrates that for the NTK to be well conditioned it suffices that the number of neurons grows as f((vn). The Odd)) and as they also assume that n = o(dl-1d then n = old)) which in turn implies du (2(m))
loose pyramidal condition on the widths implies dz-1dz-2
The rough strategy used by both Bombari et al. (2022) and Nguyen et al. (202I), 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 layerwise decomposition of the NTK matrix. This second step is erchitecture-depeneen 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.
3 Shallow networks
Here we study the smallest eigenvalue of the NTK of a shallow neural network. The parameter space P of this network is Rdd Xdo x dh and it is equipped with the inner product
(W, v). (W', ,')) = Trace (wr")")"))))
W') + to"
3

---

For convenience we sometimes write d = do. The neural network R x P - R is defined as
d v
[(; W, 0)
(2)
vdi 1=1
where W w1, Wal 1 E R xdo are the inner layer weights, = [11,- ... Ud. 1 R the outer layer weights, and (W, v). We consider the ReLU activation function applied entrywise with (2) = max 2). The derivative & satisfies (z2) = 1 for 2 > 0 and o(2) = 0 for < O. Although not differentiable at 0, we take o(0) = 0 by convention. Unless otherwise stated we assume that the entries of W and are drawn mutually iid from standard Gaussian distribution ((,1)), Our main result for shallow networks the following theorem.
Theorem 1. Let 2 3. E E (0, 1), and 8, E (0, 22). Suppose that "1.'." In E S are 5-separated and ming4k ||=; xxel S 8. Define
A 1+ (log(1/6) -3 log(d)
82.
d1 2 2|X|2 log ". then with probability at least
X 2 Amiu (K) E 8'.
A proof of Theorem 1 is provided in Appendix C.7 Suppressing logarithmic factors, Theorem 1
implies that d1 = Ω x x suffices to ensure that Amiu (K) = (dd, and Amin ())
O(5") with high probability (note the trivial bound | 2 < X || S n.). We emphasize that unlike existing results i) we make no distributional assumptions on data, instead only assuming milder 5-separated condition, and ii) our bounds hold with high probability even if do is held constant.
few further remarks are in order. First, the condition dg 2 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
becomes vacuous for do However, for dg 2 analogous bounds could be derived using more elementary tools while the case dg is of little interest as only trivial dataset is possible. Moreover, data in S! could be embedded in S since we do not impose any distributional assumptions.
use Theorem to bound the smallest eigenvalue of the NTK for data drawn from the uniform distribution on the sphere by bounding 5 with high probability in terms of n and d. We use that 5 = (n -2/do) and 8' =O 2/da) with high probability. We direct the interested reader to Appendix C.8 for further details.
Second,
Corollary 2. Let 2 3, 2 2, E E (0, 1), æt,
In U((8-1) be mutually iid. Define
log(n/E) log(d)
33
2 1/(d-1)
A 1+
n
df 2 } (1+ m+Hog((/e) log " then with probability at least 1 over the data and network parameters,
[lo([1/)) n2
1/(d-1)
Amin (K)
The above corollary implies that if dodı 52 (n (4// (1))
1)), then with high probability Amin (K) Ū(n -4/(do-1)) and Amin (K) Ö(n 22((o-11)) In particular, for data sampled uniformly from sphere, the scaling du 2(oog n) is both necessary and sufficient for Amiu (K) be é(1). In particular the bounds are sharp in this case.
3.1 Proof outline for Theorem
Recall the definitions of F(0) and K in (]. For the choice of given in ( straightforward decomposition of the NTK with respect to the inner and outer weights gives
K = K + K2.
(3)

---

where K VwF(()'V and K2 = V,F(O))V,F(()) Ji (WX) As both K₁ and K₂ are positive semi-definite,
Amin K
Amin (
Amin (2);
see, c. 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 Amin (K) and Amin K2) in terms of the smallest eigenvalues of their infinite- width counterparts, see Lemmas] 3 and beloww which act as good approximations for sufficiently wide networks.
Lemma 3. Suppose that ai,."" In E Sd-1 Let
A1 = Amin (Fu-u(s--) (ā (x u)) à (u x)])
If \ > 0 and d1 2 x 2 log " then with probability at least
Amin (K1) 2 A1.
Lemma 4, Suppose that æı," ... En E Sd-1 Let
X2 ddmin (Bu-U( [o uu)ooo'' x))).
If A2 and di 2 log
m Az
log (e), then with probability least
A2
Amin K2 A2
We prove Lemmas and 4 Appendices and respectively. Observe that while the parameters of the model are initilizzdd 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 possible the case of Lemma B to the scale invariance of ē while for Lemma it possible because a is homogeneous.
2) Interpret the indinite-width kernel in terms of a hemisphere transform. Next, for given X and vi E { {Vdo, à) define the limiting NTK K E RR
E Eu--U(8--1)
( (x u) 2 (u
(5)
Consider a fixed vector z E gn-1 and interpret the Fuclidean inner product (xb(X z) as a function u E gd-1, It will prove useful to think of this map as an integral transform. To this end let M($ denote the vector space of signed Radon measures on gd-1 and fix sb E ((Vdo d}. For signed Radon measure μ E M(Sd-1)) we introduce the integral transform Tep: Sd-1 + R. defined as
1(-, ((u,, dd)())
(ToP) = -ga-1
(6)
Note for vi {Vdo, )} this is hemisphere transform (Rubin 1999) as the integrand v((u,) ))) supported on a hemisphere normal to u. We provide background material on the hemisphere transform in Appendix [ Let Mx C M denote the space of signed Radon measures supported on the data set {æ1, ... }. For each measure E Mx there exists a vector E R such that We write Plz indicate this
J E 2:02; where 6n is the Dirac measure supported 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 E Rddx and ib E (Vda, d). For all z E R", (K 2, 2) Mz Moreover,
Amiu K
inf ||
||T 112.
5

---

3) Bound the hemisphere transform norm via spherical harmonics. We proceed to lower bound |Te for all x E RR. Let 12 denote the Hilbert space of real-valued. square-integrable functions with respect to the uniform probability measure on Sd-1, and let C(S I 1s denote the subspace of continuous functions. For μa M) and g E C(S we define
(m.9) [
3d-1 g(z)du(())
If 91,-. 9N E L2d are orthonormal, in particular consider gr. spherical harmonics, then via a Bessel inequality
n Σ
|T>M2 2 Σ pT 9a)1
Σ (Mz, To
Σ
Importantly, TΦ is self-adjoint (see Lemma 17 in Appendix B for details) and the spherical harmonics are eigenfunctions of Tg. i.e. Taga Ka9a- A summary of the key properties of spherical harmonics needed for our results are provided in Appendix A.2 Therefore
N
N Σ 0=1
Σ
(Zoga)(z))zz
(
2 min R Dz
a=1
i=1
where D Nx is matrix with entries
[D] ai 9a (x:)) As result
Amin K 2 min 2 min (D).
4) Bound the hemisphere transform and spherical harmonics on the data. The following result shows that if we let the functions (9o)aE[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 He denote the vector space of degree-r harmonic homogeneous polynomials on d variables.
Lemma Suppose 21. En gd-1 are 5-separated. Suppose that B E {0, 1} and that R E Zzo
(d-22)/2 (d-2-12)))2 where C > O universal
such that N EP= dim dim satisfies N C ((*) constant. Let 91,"-" ,9N be spherical harmonics which form an orthonormal basis of ① D Hid
If D'D E NxN defined as Dai = (2,)) then mmin (Din(D)
T
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 measure.
Lemma 7. Let d 2 3 and suppose that æ1,
In E gd-1 are d-separated. For all z E R with
|| < then
d 118) log (1)()/)) log
82
if à
33
84
if = dda.
proof of Lemma / is provided in Appendix C.5
The lower bound of Theorem [ follows by
bounding Å1 defined in Lemma 3 using Lemma
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 Amin ( as the (Sd 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). 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 sigmoid, such quantities appear challenging to compute.

---

5) Upper bound. The upper bound of Theorem I is simpler than the lower bound and hinges on the following calculation. Let 2;, 2y be two data points. Then
min (K) - 1 ( - ex) K(e; ex) = [Vof(x)) 2
Vof(=x)1*.
Therefore it suffices to upper bound the norm of Va)(æ,) - Vol(ax). We choose i, k E [r]
such that mi Fy are the two closest points in the dataset. We then translate this into a statement about the gradients. If ||a æxll S 6, then with high probability over the network parameters.
(Vffaa)V(((( g (see Lemma 29 and we arrive at the desired upper bound in Theorem
4 From shallow to deep neural networks
Our goal here is to detail just one approach as how the results of Section can be extended to deep networks. To be clear, here consider fully connected network with input dimension dg and L layers, where each layer has width d1, .1. dz respectively and dz = 1. The parameter space P is a product space of matrices I [dd -1 equipped with the inner product
(W1,
WE), (W), Wi) Trace Trace(W?"W.))
The feature maps ft : Rd x P + Rd of the neural network are given by
x
1= 0
f1
o [(Wiff--1(:: 0))
E [. 1] 1= L,
Wi (2;
where Wi E Rdxx: for all I E [L]. 0 = (W1,... Wr. and a is the ReLU function x +
max(0, applied elementwise. We define the network map to be the final feature map multiplied by a normalizing constant:
II
JL-
1=1
Given n data points æ1 ... In. we bound the smallest eigenvalue the NTK ① associated with this partieular choice of f.
Theorem 8. Suppose E (0,1/3), 8 (0, 22. do 2 3, the data I Ø2, In E Sdo-1 is ò-separated and define
== 1 do log (10))
-3
82.
log do
With regard to the network architecture, let L 2 3, di 2 di+1 all I E [L- dr.-1 2 2 log (اا) and d, 2 X log (+) log (+). Then with probability least over the network parameters
A S Amii (K) S
We emphasize that these bounds make no distributional assumptions on the data other than lying on the sphere and being 8 6-separated; in particular, they hold even for constant dg. Indeed, we consider do as some constant then Theorem g implies that if the first layer is sufficiently wide, di = Q(nd
then with high probability over the parameters Amiu (K) = 52(84) and Amina (K) = O(1.
few remarks are in order. First, the pyramidal condition on the network widths could be relaxed by more directly borrowing techniques from Nguyen al. (202T). We adopt this condition the advantage of making the dependence of our bounds on the network depth I. clearer. Second, compared with Theorem [ and ignoring log factors, we observe the lower bound differs by factor of 82. This arises as a result of the smallest eigenvalue of the feature Gram matrix F F; being equivalent to the Jacobian of a shallow network with respect the second layer weights, not the inner layer weights, which has a different lower bound as per Lemma / For reasons apparent in the proof outline below the lower bound on Amiu (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 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. (202T) and Bombari al. (2022), we refer the reader to the proof outline below for further details.
has
7

---

4.1 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 introduce the following quantities. For I [L 1] we define the feature matrices F; E IR by
F (I())) fi(
For / E [L - and a E Rdd we define the activation patterns 2x(x)) E {0, 1 (0.1) to be the diagonal matrices
[x
Finally, we let 1, denote the vector of all ones in R"
Un E Rd be nonzero. There exists open set U C P of full Lebesgue measure such that (() is continuously differentiable on U for all [n]. Moreover, for all 0 E U the NTK Gram matrix K defined in ④ with network function 7 satisfies
Lemma 9. Let æ1.... ;nn
L-1 di
L-1 K-
II
K-Σ
(F Fi)
@ (B,+)
2
1-0
where the ith row of Bi E Rux defined as
(x(x))
(IIk=44 WT
WT, lE [L [-- 1= L.
Bik
In,
For completeness prove Lemma in Appendix D.I Observe each matrix summand in Lemma positive semi-definite (PSD) and recall for any two PSD matrices and B one has Amin (A B) Amin (A) Aminn (see e.g. Horn & Johnson 2012 Theorem 4.3.1) and Amin ( (A A B) >
Amnin ( (A) minie(m) Bla (Schur 1911 Therefore
(--1
d 2
II
Amin (K)
Amin ((F) Fi) O (BLIIB Amin (F min ie(n)
[2
In order to upper bound the smallest eigenvalue we follow Nguyen et al. (022) and analyze the Raleigh quotient R(u)= Iuu and therefore Amiul K)
Ku In particular, for any nonzero u E Inn have Amin (K) R(u)
S R(e,) = [K] for all i E [m]. As a result
de |I 1=1
L
L-1
Amin K)) s
Σ (FFF) @ B B
Σ [((a)))
2
Combining the upper and lower bounds we have
L-1 di
Amin (F
min sE/m]
[B2k, < Amia K)
II
(f [f(=:)]][[[]lll) (8)
2
where the right hand side holds for any E [n.. Based on we proceed first by bounding the norm of the network features. We achieve this via an inductive argument, bounding the norm of the features one layer with high probability, and then conditioning on this event bound the norm of the features at the next layer with high probability.
Lemma 10. Let x E gdo
L 2 and I E L
1). df 2 12 log(I/e) for all k E [1] then
dn
dn
II
$ <11f(())) se
II
2
2
holds with probability at least - over the network parameters.

---

A proof of Lemma I0 is provided in Appendix D.2 Next we derive upper and lower bounds on the backpropagation terms [B].. Our strategy for this as follows: for I 2]. let
()))) Ex) (Π WT (x)) and observe
[B:].:: (a,
Since æ; E 8da-1, is sufficient to lower bound [| W 13 for an arbitrary a E gdo As the vector W E R is distributed as WT ~ NN d Id...), following Vershynin (2018
Theorem 6.3.2) we have that for any A E I2 xdg-1 and 2 0
C122
P(II I1 || t) S 2 exp
||-|122
for some constant C >> 0. As result, with t = | then
3 A
2 1 - expexp -C || ||
| S AWIII <
In order lower bound ((x W | with high probability over the parameters it therefore suffices (x) I| and [[S((z)]]]- These bounds are provided in Lemmas 34 and 35 Appendices D.3 and D.4 respectively, With these two lemmas in place can
to condition on appropriate bounds for S
bound ( WE 2
Lemma 11. Let æ E gdo-1, suppose L 2 3, de 2 for all k E 11 and d 2 2" log (+).
Then, for any I E [L - 1]. with probability at least E over the network parameters
((())
2 22-4441
II dx-
By combining Lemma lower bound of (8)
11 with union bound we arrive at the following corollary, relevant for the
Corollary 12. Let we E gdo-1 for all [n], L 3, di 2 det for all I E [L- 1] and
dL-1 2 2- log
nL)) Then, for any E [I 1]. with probability at least 1 over the network
parameters
L-1
min =E(m)
[a 12 2 2-L
II
dR-
The first-layer feature Gram matrix F F; the deep case is identically distributed to K₂ in the two-layer case; see (3) and the related definitions. Therefore we can apply Lemma lower bound the smallest eigenvalue of Ff' Fj. This, in combination with Corollary [2] yields the lower bound of Theorem 8 The upper bound follows by combining the bound on the Teature norms provided by Lemma 10 with the bound on the backpropagation terms given in Lemma IT detailed proof of Theorem is provided in Appendix D.6
5 Conclusion
Summary and implications. Quantitative bounds on the smallest eigenvalue of the NTK are 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 do scales appropriately with the number of data samples n. This work plugs important gap in the existing literature by providing bounds for arbitrary datasets on the sphere (including those drawn from any distribution the sphere) in terms of measure of distance between data points. Furthermore, these bounds are applicable for any do. in particular even do 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 upper bound on the smallest eigenvalue of the NTK for deep networks in Theorem does not capture the data separation. Finally, a mild limitation of this work that we require the data to be normalized 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 infegral transform on the space I, (.R 1u) rather than T.2()d=1), where lr denotes the standard Gaussian measure (since the weights are drawn from 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.
Acknowledgment
This project has been supported by NSF CAREER 2445630, NSF 2212520, DFG 464109215 within SPP 2298 Theoretical Foundations of Deep Learning, and BMBF in DAAD project 57616814.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 2019. URL httpss:/prroceeding mlr. arress/v9/all1 /wl////alle--/// waannn-hh99a..a html
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 09-15 Jun 2019a. URL URL httttts:///ooccedddnggo mlr press/v97/ aw17//9rra199..... html
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b. URL http:pt:://poceeddiiigggo .eurips cc
dbc4d84bf http:///eebbeee2222ee1eeeeeeaaae
Paper .dff
Sheldon Axler, Paul Bourdon, and Ramey Wade. I theory, volume 137. Springer Science & Business Media, 2013. URL /ttps://s///o 10. httttp//.ooo..or////.0100777111-
Keith Ball. An elementary introduction modern convex geometry. Flavors of geometry, 31:1-58, 1997.
Arindam Banerjee, Pedro Cisneros-Velarde, Libin Zhu, and Mikhail Belkin. Neural tangent kernel at initialization: Linear width suffices. In The 39th Conference on Uncertainty Artificial Intelligence, 2023. URL /ttp:tttts///pperrrriie http:///ppeeeeeeeeeeeeeeerrrrrra
Ronen Basri, David W. Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems 32, pp. 4763 4772, 2019. URL https: /ttp::///rrroo http///prreeenn.s.eeee////e www.ddiiinnnnniiiiss.....e.. newrips cc/ Abstract html
paper http:///////aaaeeee/////////2220
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 685-694, PMLR, 13-18 Jul 2020. URL https://procsedingss mlr. .press// u119/basri200 20a html
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks kernel regimes. In International Conference on Learning Representations, 2021. URL ptttps://openreviee .net// forum? aosimidd-aDoosTTXXX00
Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli. Memorization and op- timization in deep neural networks with minimum over-parameteriizaion..
Advances
in Neural Information Processiny Systems, volume 35, pp. 7628-7640. Curran Associates, Inc., 2022. URL https: httppe///oooeeeiingss.... nwwrips....pp...e.. cc/ cctp.per..pppppeeeeeeee halppappppeell__l/lllllllllpppee filles/paperr/222//Eiie. 122746f0ae22dddfff0000dddddogg Ceapper-ooffeenneeeppe
10

---

Benjamin Bowman and Guido Montúfar. Spectral bias outside the training set for deep networks in the kemeel regime. In Advances in Neural Information Processing Systems, 2022. URL
httpss://ppereviiii http://pppearrreeeeeeeeeroo/o//o .ett:/Eorrumm/d-a0012222222
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp.
August 2021. htttss/tts:/// 1/0g://////.o///////
24963/1jcai. 2021/304
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpps://proceedddngg hnwppp/roooedddnggse..e.rrpppppp neurips...... cwtturip.ccppaaappe httc:papee_ffleeppppeeeeeeee /ttpe//ee///ppr//0///// bec116667444411266677772666---33
pdf
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. In Advances in Neural Infor- mation Processing Systems, 2021. URL
net/forunidd-De Aawwwwww
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learming Research, pp. 1675-1685, PMLR, 2019a. URL URL.httts://procceedng. httppp/ooooeeoaa......rrrss///// wwwpp/esre.///./p html
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019b. URL htttps://ppenrrr//// wtwpeerrrooooo.ettooouuurtticdd wwtp:oeenndddd-eeeeeeeeeo
Costas Efthimiou and Christopher Frye. Spherical harmonics p dimensions. World Scientific, 2014. URL httpt:t//oii.orrrgg 111.6/.0000//111111/99999999 1142/9134
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear- width neural networks. In Advances in Neural Information Processing Systems, volume 33, pp. 7710-7721. Curran Associates, Inc., 2020. URL
nwwrips. neurips.cc/paper/
pdf
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the Laplace and neural tangent kernels. In Ad- vances in Neural Information Processing Systems, volume 33, pp. 1451-1461. Curran Associates, Inc., 2020. URL htttps://proceedingg cttprr/p..cc/ppppe/////////e 1D0G5122445555555544444444151333
pdf
Izrail Solomonovich Gradshteyn and losif Moiseeviihh Ryzhik. Table of integrals, series, and products. Academic press, 2014. URL htttps::/bbb.orrr/000001/////// 01101////0210000043033330 64839-5
Roger A. Hom and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, vol- ume 31, Curran Associates, Inc., 2018. URL https: / htttpppp//prroceednnggs
www.eene..iiiieee. cctiipssc/ppppeee cc/paper. paper_ .
Hui Jin, Pradeep Kr. Banerjee, and Guido Montúfar. Learning curves for Gaussian process regression with power-law priors and targets. In International Conference Learning Representations, 2022. URL httpps:/opeereviess
het/forrumiid-KeIIE.. -goB
Kedar Karhadkar, Michael Murray, Hanna Tseran, and Guido Montúfar. Mildly overparameterized
ReLU networks have a favorable loss landscape. arXiv:2305.19510, 2023.
B. Laurent and P. Massart. Adaptive estimation of quadratic functional by model selection. The Annals of Statistics, 28(5):1302-1388, 2000. URL. /https:: sittts://doi.. http::///.o....////.////// 1214/ /
1015957395

---

Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL URL.tttps:: htppp:::d...ooeeons....... pttpsarrrp.eee/pppp///////////// pttppp/p///11//fllee
pdd
Jachoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman No- vak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: empirical study, In Advances in Neural Information Processing Systems, volume 33, pp. 15156-15172. Cur- ran Associates, Inc., 2020a. URL
www.:ngg..nursr....mo pdf
Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang. On correctness of automatic differen- tiation for non-differentiable functions. In Advances in Neural Information Processing Systems, vol- ume 33, pp. 6719 6730. Curran Associates, Inc., 2020b. URLLattps:/pprocedangs wwwpiinnnnn....reeeeeee..e.rerre htt.:///2.6007777666666666666661
e05c8882296961771000 Paper pdf
Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics & Statistics, 4(1):66-70, 2010.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. In Advances in Neural ran Associates, Inc., 2018. URL Neurral Information Processing Systems, volume 31. Cur- i neur ips. cc/paper.........ppp /ilesspaperr pdf
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. In Advances in Neu- ral Information Processing Systems, volume 33, pp. 15954-15964. Curran Associates, Inc., 2020. URL https://proceeddngs wwturips.ccpaapa.. files/ http///pppee/e//////2// b7ae8fecf (Bwcee00000c00000000000000000000
pdff
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022. URL https: / /www. sciencedirect. coom/science wttss/ccieeeeccceeeeee p21/$10635203210001000 Special Issue Harmonie Analysis and Machine Learning.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memo- rization and generalization under lazy training. The Annaly of Statistics, 50(5):2816-288) 2022.
URL tattpss//dolle org/10 1214/22-
Michael Murray, Hui Jin, Benjamin Bowman, and Guido Montúfar. Characterizing the spectrum of the NTK via a power series expansion. In The Eleventh International Conference on Learning Representations, 2023. (tLhhttps::// httpps:://penneeree...ttt wtt.://www....t.oooooooooooaatt.
Paul Nevai, Tamás Erdélyi, and Alphonse P Magnus. Generalized jacobi weights, christoffel functions, and jacobi polynomials. SIAM Journal on Mathematical Analysis, 25(2):602-614, 1994.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep ReLU networks with linear widths. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8056-8062. PMLR, 2021. URL https://proceeednggs mlr. hatps////1//nggunnnee11 html
Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer fol- lowed by pyramidal topology. In Advances in Neural Information Processing Systems, volume 33, pp. 11961-11972. Curran Associates. Inc., 2020. URL https: :tttt::://ppccceeii http:///ppoeeenn....e www.:nngs..urrip..oo Paper .dff
Quynh Nguyen, Marco Mondelli, and Guido Montúfar. Tight bounds on the smallest eigenvalue of the
neural tangent kernel for deep ReL.U networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8119-8129,
PMLR, 28-24 Jul 2021. URL https: htttss://pooceeaiiiiiiee mir. pwwpp/ aatess/vv19///e w139/nguyen91gggggg html
12

---

Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overpurameteriizttin: Global conver- gence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Infor- mation Theory, 1(1):84-100 105, 2020. URL pettpp::/doi..rgg///
1109/JSAI] 2020 299133992
Boris Rubin.
Inversion and characterization of the hemispherical transform. Journal d' d'Analyse Mathématique, 77:105-128, 128, 1999. URL
Schur. Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen. Journal für die reine und angewandte Mathematik, 140:1-28, 1911. URL
http://eudm1..rrg http:/d/w...rgg///////3//31// 149352
Robert T Seeley, Spherical harmonics. The American Mathematical Monthly, 1344
1966. URL htttps://aoi.or/////// 1080/ 01880/00098990.00 1966. 11970927
Joel A. Tropp. User-friendly tail bounds for sums random matrices. Foundations of computational
mathematics,
2012. URL https:t/ttts..oggeeeso 0000//0000000000000000---0-09990 httpp//..../aaa.ro//./....///...
Maksim Velikanov and Dmitry Yarotsky. Explicit loss asymptotics in the gradient descent training of neural networks. In Advances in Neural Information Processing Systems, volume 34, pp. 2570-2582 Curran Associates, Inc., 2021. URL httpps::/proceeediinni neurgis......ppp...... oc/paper_
Roman Vershynin. Hlihh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. URL https:://ai..rr//....
9781108231596
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Proceedings of the 20th International Conference on Artificial Intelligence and Statisties, pp. 1216-1224. PMLR, 2017. URt.httts::/pproceeeeii
mlr press/v54/xiee xiel7a....... 1tmm..tmm html
Ziqing Xie, Li-Lian Wang, and Xiaodan Zhao. On exponential convergence of Gegenbauer interpola- tion and spectral differentiation. Mathematics of Computation, 82(282):1017-1036 2013. URL
https://doi.. org/ 10. 1090/ 00090//50225-51--202222
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neu- ral networks. In Advances in Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc., 2019. URL https://proceeddngs wwwpiiinnnnnneuiispeeee.e nww.ineu.rcc..ooo wtt.mrpps..ccppppe/////////../..
pdf
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine learning, 109(3):467-492 2020. URL https
13

---

A Background material
A.1 Concentration bounds
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 > O, and let Zı," Zm E Igax be iid symmetric random matrices such that Z1 RI almost surely. Then
Crnmmin (IE (21)
P
Amin
Zz jml
S 2
Amin (B[Z)))
nnep
R
Here C > O is universal constant.
Proof. By Theorem 1.1 of Tropp 2012). for all > 0
m
P
Aii
S (1 Amma (211)
m
))
m
P
Amin
Σ Zj
S S1 8)Amio
Σ E(Z
Amina (Ege, 18(2,))
e 8-8
S n
(1 8)1-8
R Amin (1)
e
(1 8)1-6
Let 8 2 and let C= = log ( > O. Substituting into the above bound, we obtain
TH Amin (B(z,)
1
2
P
Amin
Zj
Amin (B(2,))
S
j=l
C'AAmnn (E (1))
exp
R
Some of our NTK bounds will depend on the operator norm of the input data matrix X, so it will be helpful upper bound || with high probability.
Lemma 14. Let > O. Let X [xi,... xn) Redx be a random matrix whose columns are
independent and uniformly distributed on gd-1, Then with probability at least E,
+ log d
X 2 1
Proof. We use covering argument. Fix 1d-1 and v E gn-1, By Lemma 2.2 of Ball (1997), for each i E [n] and i 2 0,
di2
P(Ku, 2 t) < 2 exp
In other words
<,) < Va Then by Hoeffding's inequality, for all t
P(Iu''xt 2 t) = ( > Uu xx) 21)
< exx (cdtt?)
(9)
14

---

where C1 > 0 is a constant.
Let "1y".. RMM be -overnng of Sd-1_ That is, "1 -MM that for all gd-1, there exists
of points in g such
M such that ||u - uyll 1. Since the (2) -coverrnn number of gd-1 is at most 12 (see Vershynin 2018 Corollary 4.2.13), we can take M S 12 Similarly, let "1.-." uN be (1) -covering of 8" with N 12". By applying union bound to (9). we obtain
IP(12 Xval for some
[M], k E [N]) S 2(12 exp (- (-Cidt²).
Hence if
+ n)) log 12 + log t
d
then
P(u2 X S t for all [M], [N]) 2
Let us condition on this event for the rest of the proof. Now suppose that u E Sd-1 and v E S
By construction there exist j E [M] and ie E [N] such that 1 uj || S and || vx I
Then
1u X
v
1 T X
( u²)²
Xvxl + |u X (v vx)
+
Ugll
|
|X|||
|| |X||| ||0 myll
1
$ +
|
+ 4
X
4
1
| + 2
|||
Since this holds for all gd-1 and E s--1 ! we obtain
X t マリ1 X||
Rearranging yields
X 1 < 4t2
n + log
S +
d
A.2 Spherical harmonics
Here we review some preliminaries on spherical harmonics necessary for our main results. For further details we refer the reader to Efthimiou & Frye (2014) ander et al. (2013) Chapter 5). Let I,2 (Sd-)) denote the Hilbert space of real-valued, square-integrable functions on the sphere $d-1. equipped with the inner product
[ g(x)/(() dS(x), 30-1
(g, h)
where d5 is the uniform probability measure on gd-1, We let C(S C L2(80-1) denote the subset of functions which are continuous. We say that function g : Rd - I3 is harmonic twice continuously differentiable and
82 g 2z,
Σ
(x) = 0
for all æ E gd-1, We say that polynomial g Rdd R. is homogeneous if there exists Zzo such that
(Axx) X (x)
15

---

for all À E R and a R Let HP denote the vector space of degree r harmonic homogeneous
polynomials on d variables, viewed as functions S + IR. Fach space HP is a finite-dimensional vector space, with
(H,)) = r (
r r++
d -
d-1
2r + 2
rr + d d-3)
2
For 2 and r E N, we define the Gegenbauer polynomials C by
L2/2
T(r - k 1/) [(u)T ()((r - 2k (2t)-
C+)) - Σ (-1)*
R=
There exists an orthonormal basis of HP consisting of functions Y 1 S 8 S dim(H4)) known as spherical harmonics. The spherical harmonics in H. satisfy the addition formula
dim dim(H))) Y (x)) dim dim(HL)) (d (d--dd)))) 2)/2 (1x, (x,xx')](rr+ 1)T(d 2)
cdr+d-2)
(2r + d - 2) (oc(d-2)/2 2)/2 (12, x²))
(10)
d-2
for all n, x' E Sd-1 In particular, from the identity (1) = T(2+4
[r20][(++]] it follows that
dim(H))
Σ
= dim(H
We can orthogonally decompose (Sd into a direct sum of the spaces of spherical harmonics:
(
H
That is, the spaces Hif are orthogonal and their linear span is dense in (Sd(S)-)).
Lemma 15. Let 5 >> 0 and suppose that x' E gd-1 satisfy ||æ x'11, ||= + x' 2 6. If R E Z and B E {0, 13, then
dimutNg g) Σ
|| ||2- x²1 ((d-2)/1 ( (2R+
+ 3 d 1) 1/2
Σ
Yd (x)
20 (x') 2
2
d-1
Proof. Let define
R
dim (
P(æ, ==
Σ
Σ
Yd
a ( (
By the addition formula (Tpp.
R
(4r + 23 + d 2) ((x x²))
IP(x, x')| =
Σ
d
(r d) dd) (d-2)/2
O
( x'))
(11)
d
P= 0
16

---

In order to bound the right hand side of the above equation, we will need a bound for the Gegenbauer polynomials C/ By Theorem I of Nevai et al. 1994) (see also equation 2.8 of Xie et al. 2013 2
for all v 2 2 2 O, and f E (0,
2e(2 + v2v) 2 2' π
T(r+201 + 22) [(2)2 -(r 1)(r +v)
(1 - ()))) =
vr + 2n)
2 + (v)
Rearranging the above expression yields
4
(t) (r + +))+))(())))(--11111 1) 12)0/22
We now substitute the above bound into ITp
(r
2-2)
1/2
(2r + -
|P(xr 2
d2(d-2) 2)/2 (2r + 3 +
1-2)
1/2
r
1-2
1' + 8 1) (x, x1)))
2
R
+ d
1/2
T(2r + 3 + 2
c x')3)(--211
2 ( [(2 + 3 1)2/22
The expression inside the sum is increasing as a function of r, so the above expression is bounded above by
R (R+d) 1/2
(1 - (x, 2')2)(d-2/4 2)/4
d
2/4-2 2 + +
r(2R + 8 + d 1)
(12)
d1/2 - (z, (2d 2)/4 2)/4 2
M(2R + 3 + 1)1/2'
2
By Stirling's approximation,
(d-2) (d-3)/2
d dd
2(d-2)/2T
x 2(d-2)/2
(d-2)//2
2
2
(d - 2) (d 2) 3)/2 (d-3)/2 (d-2)/2
x d 1/4((d 12 (d-22/22
x d 1/T(d - 1)
Substituting this into 12
yields
1
p < d1/4(1 (x, 2222))(d221)) 2)/4
[(d 1)
d//4
(R + (R+d)1/2(1
(x, x2)))
+
1/4
(2R 8 8+ - 1)
1/2
(R + (d)z)/2(11
(x, x²) )3)))(2)2)//
d-1
2R + 8 + d- 1)
1/2
(x. x')2)(d-224
d-1 1
Since x, x' e 1
(x,, ,²² (1 + (a,, x1) x'))
x x || x x011
4
17

---

To conclude, we rewrite
(((,,r') -(d-2)/4
88 2
(2R 3 d - 1) 1/2 d-1
B Preliminaries on hemisphere transforms
Let M( denote the vector space of signed Radon measures on gd-1, We denote the total variation of by |p]. We have a natural inclusion (,2()(-1) C M(S by associating a function signed measure y defined by
M m{E) = S g())dS(z))
If J E
MS and E C(B we define the pairing (1, g) by
- -()__(()))((( g(z)du(x))
(p,g) =
This agrees with the usual definition of the inner product on 12(()(11) when E (2 Fix tb E (Vdo,o), d). ja E M(S we define its hemisphere transform Rubin 1999)
Ta
s + by
(TeP)(E) = [ (((5 dd)().))).
As is the case with many integral transforms, a hemisphere transform increases the regularity of the functions it is applied Lemma 16. If E M(S--1), then Typ E (2((8-1), Ifg E (2 then Twg E C(SL-1).
Proof. Suppose that MM(S-1)). Then
2 [ (I)N) gg 1sse ub x))(()))
dS(E)
((EE))))d
dS(E)
---1
84-1
---1
d' ddd
38
( (i(gdd-122 122
00,
so Th (2(8)-1)) Now suppose that g (2( and va c. Suppose that E' gd-1, and observe that
dS((# E gd-1 (x, o, (x, s 0}) =
(rccos((E,$'))
2n
Similarly,
dS((x E gd-1 (z. k) s 0, (x. > 0}) = Arccos((E,E5 (E))")), 2
so
dS((x E gd-1 sd-1 :0((x,E)) # )((x,'))) = arccos ((E,')).
18

---

We apply this calculation to bound the distance between (e)(E) and Tog(E))
Tog(E) Tog(E'1= = | ga-1 o((z, (((1,
[ o((z, (((x)5))(())d((a))
[ | (0((x,
E)) (((2)))))
$ 1191112 ( 10( E)) ((x, (1))=)))))))))))()) {d))))((x))))))
1/2
||ll|a> (dS((x E s ó( {)) + 0( E\1)) 1/2
V (rrcco(((EEE))
Here the third line follows from Cauchy-Schwand As É + f arccos (5. E\) -> and so (T (e'()") + O. Therefore, Twg E C(S
Finally suppose that g E 11 and vi- = vda. For all & E @d-1
[d, {))(()) S vdlg(z)] E 1)dd))). So by the dominated convergence theorem, for all g' E Esu-1,
lim Twg(E) = lim & Jgh-1
(ado(ae, (x)()))
5-
lim (() 1E
(()((()))))(
Jg
Tog(E")
Therefore T&g E C(Sá-1).
By the above lemma, for any μ M( and g (S( the expressions (Tef4, g) and (j,, Tog) are well-defined and finite. In fact, they are equal to each other.
Lemma 17. Suppose that E M((d-11 and E (gd Then (Tep,g) Twg).
Proof. We compute
(Tep, = /
84-1 (T+W(E))(E)dS(E))
8a-1 332-1 (((x, (((aa)))a((()u))dssss)
ga-1 (1(2 ((le))))l(()dS((ddd
Ss Tag(a)du(())
(M, Tog)-
remains to justify the change in order of integration the third line, This follows from Fubini's theorem and the calculation
SSL. Sm. (((({,))))((()ss((())))))))
<
30-1 Jga- Valo(t)lsS(()pp(())
1-1
where the last line follows since g e (2( C (S4-1))
19

---

In order to characterize how hemisphere transform acts on (Sd-11 and in particular on the
spherical harmonics, we will use the Funk-Hecke formula (see Sceley 1966) which states that certain class of integral operators on gd-1 has an eigendecompossiiinn of spherical harmonics.
Lemma 18 (Funk-Hecke formula). Ler tb [-1,1] - IR be a measurable function such that
S [v01((11 - -13 (3)(d-3)/22l < oo.
Then for all g E Hd
1S (z) - c.,g(E),
where
T(r + 1IT(d) - 2)r G.d - ( S -1)0-
We will now use the Heeke formula to compute the coefficients Cr,d in the cases where v/ = do and di 5. In the following calculations we will use the Legendre duplication formula
+ 2) )) = 21- 22 VTT(22)
and Euler's reflection formula
r(1- - 2))
π
sin
Lemma 19. For all d 2 3 and r 20,
S C(d- c(d-2)/2(t)( - (2) 3)/2
v (ب 2r - (r + 1)I (1 (1- ((t)
and S. (0)(
(dl + - 2)T اله
4r - 1)[ (3م )
Proof. We apply the following identity (see Gradshteyn Ryzhik 2014 Equation 7.311.2):
[ (0(1
r(2u ++ 2+
1)
By the Legendre duplication formula, we have
r 1 (
so we can rewrite the above equation as
L (2)) 222++++ +
(13)
Substituting = -r/2 and v = = into
13 yields
[. cla c(d-2)/2(1((1 - (d)(d-33/2 21 - 2]l 21- I(r (+))
(d 2) d-1
which establishes the first identity of the claim.
Substituting (1 (1- r and == (d - 22 into 13 yields
[. (()-2)/2 - -P)
( + 2)r (d-ه)
4r 2) (3 I(r + 1)r 1) (dtrnl)
which establishes the second identity of the claim.
20

---

Lemma 20. Suppose that E Ht and d 3. Then for all r 2 0, Tog = cr,dg. where
Crd 2T (1 5)
Moreover, if0 r S R. then
102+11,0 2 [ r (2
2xI (+2((t1)
Proof. Let E H.p. By Lemma 18
Tog Gr.d9-
where
T(r 1)T(d 2)T
((1))(422/2(((111 - -0a1 P2yid
Cr,
(5
I(r+ 1)d(dd 2) (4)
L.
C(d-2)/2 (t)(1 -
(=I(d-2++)) (5
By Lemma 19 this is equal to
[(r + -) (
-
v 2)1 (1د
r (
- 2+ (-ك 21 (r + 1)1 (1- (1- (
d+r
21 (1 - (
d+r
claimed.
Now we proceed with the second statement. We claim that whenever S S R.
|02R+1,|| $ |02r+1,d]-
We prove this by induction on R. For the base case R the claim trivially holds. Now suppose that the claim holds for some R Then
r
(2(
2T (1 21++3)
r
2/2+3 +
2
2R+1 1
r
2
21 (1 2R+1 2
(2R+1 + r
2R+1 9 (
2R +1
|02R+1,a|
2R + 1 +
|02R+1,l
102r+1,0l-
Hence by induction |c2 < 12 for all 0 < < R. Now suppose that 0 r S R. By Fuler's reflection formula,
r
C2R+Ld 2r (1
28+1 2
2R+1
2
T (5) sin (7: [.2+++1
2
2n (2R+1
1 (1) (-1)a1 "T (2R-1)
2TI (2R+1 +
80
102 2 102
r I 22+11
2 r 2+2 2
21

---

Lemma 21. Suppose that E Hi and d 3. Then T Vāng cr,d9, where
Vdr
Cr,d
4
Moreover, if0 r S R, then
(2) r (21-1) dT
22
4Tl
d+2R+1 2
Proof.
The proof is analogous to that of Lemma 20
Let g E Hpd By Lemma 18
T T cr,9
where
+ () [ (4 -12((d-3)222
Gr
VTI(d 2 +) (1-1)
( 2)r 1g)
(C(d-2))2(t)( - -12)
V=I(d- r)r ( .0
By Lemma 19
this is equal to
(r - 2)r
v 2)[ 1-
Vd (
4T - 2) 1)[ (3
d+++1
(3 r
(d
2
claimed.
We claim that whenever 0 S < R,
[22R S |c2ral-
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 2
Then
dr
(22(1+1)|
4r 1- 2Rt
r 2+2R43
(1-2R) ViT (5)
41' (1-2R)
1+2R+1 I' d+2R+1
2R
C2R + 2R
S C2R-
Hence by induction |c2R| reflection formula,
|22l for all
S < R. Now suppose that 0 < r S R. By Euler's
C2R
41' 3-2R
1+2R+1
Vdl (d) sin (T
21-1
2A-1
2
4.r
d+2R+1
(-1) dr
r
2R-1
2
4Tl d+211+1
So
(c2r,al |C2R,d
Vdr
22-1
4mr
2
22

---

C Proofs for Section 3
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 E _ddox,, then
Amin ((a.La) [or (x" u) (X"w)
(w x)]) = doomin (Bu-u1800-1,0 (X"u) u) (u' x)])
Since the distribution of w is rotationally invariant, we can decompose a |lll| uniformly distributed on gdo-1, and and u are independent. Then
Proof.
au, where
Amin (Ew-N(0n.La) [or (x" w) a (w" x)]) = Amin (E
o (x w
o (w" x)])
Amin (E Ia'o (x u) (u x)])
Ami
(E [a"] E [ (x
(u' x)))
= do
[E (X"u) x)])
Lemma 22 useful 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
Lemma 3. Suppose that æτ, ... In Sd-1 Let
A1 = Aman (Eu-t((8--1) (o (x" u) r x])
and di 2 2 X 2 log 2. then with probability least
Auiin (K1) 2 d1.
Proof. By the scale-invariance of o
Å Amin (Buns((aade) (ō (x"x) ò (u x))x)))
For each i E [n]] and j E [di].
V wy fa::)
Vdz n1 (1007 axi)) ai
and therefore
d
K1 di j=1
Zjr
where
2, (o (x) (x)
w)) (w x)) c xx"x).
For each j [d1]. let 10,1) be random variable taking value I if loy| < and taking value 0 otherwise. Since by is a standard Gaussian there exists a universal constant C₁ with U[ C₁ for all j. We also define Z LjZμ. Note that Z 0. and by the inequality
Amax A ④ B) max, Amxxmmxx( (B),
|| = |5 (ā (x" w/) á (w; X)) o (x"x)]
< max
(5 [ (x"w;)) à
x
vn
Ejoã0 (w) x.) / X
= max
<lnn
< |||2
23

---

Furthermore by the inequality Amin (A ② B) 2 min; A ii Amin (B),
Amin (E(Z)))
Amin
(E [Snu] (o [x* w. (w) x))] (x* x))
(xx))
2 min
E [5 (a (xx w (w) X
min iE|n]
(x*x)
Ami (E [5 E [ (x wy) o (wf x))]
min |,,||
Amm
E [(o (x" (X"w,) à (w)
C1d1.
So by Lemma 13 for all /. 2 0
d Σ
1
Amin
Z
<CiAi
PP Amin
Σ
E[Z2]]
d1
di j=1
j=1
C2d1 |||1
S exp
where C2 > 0 is a constant. Since Zj = Z for all j E [d1], if 2 c2si
|
2x|221og log (?), then
1 Σ
C2d1d1
P
Amin
Z, s Sid
Snexp
(-1Xip²
di
j=1
S.
C.2 Proof of Lemma 4
Lemma 23. Suppose that .1,- En E Sdo-1. Let
A2 dodmin (Eu-U(8'o- 1) [a(X"") u x)]).
If A2 > 0 and di 2 Xa log
log ()), then with probability at least 1 - 6, Amin (K2) 4.
Proof. Note that by Lemma 22
A2 Amin (Bm~N10u.Ta) [o (X" w) a (w X)])
For each i [ni] and j E [d1].
Ve, f(z)( = (w xi)
Vdn
and therefore
d
K₂
di j=1
where
Zj = a (x* un (X=rr,)
(nn x).
By Vershynin 2018 Theorem 6.3.2), for each j E [d1]
x
x w
|ellss + x|x 1|
X + |X 1|
X IF
vn.
24

---

So by Hoeffding's inequality, for all t 2 0
PP X w/y 1| 2t)= =P (| wy 2 vt) - (- (-Cnt
Cit
2 exx
(14)
for some constant 1 > 0. Let c
log بي_ For each [dg] let & E {0, 1] be random
variable taking value if || x T w 12 s and taking value O otherwise. Let Z = E Zj. For each j E [m]] Zj ž 0, and
|z/| = ||م, (x" ('/ww)) a (w]x)l
= ||5,o (x"w;))] 12
S S.
Moreover,
E [[ E(Zj]|
[ [1 E,)a (X" w))) [m) x)
S [(1 E4) ||
(x w)) a (w) x
E (1 E,) || (x w.y) 11?
(1 - Eg | (//e [1"]
2 E
P (1Ix"00) w,ll? 2 1) di
Cit
$
exp
dt
n
2n
C18
cxp
C1
7
A2
Here used (14) in line 6. By Weyl's inequality,
da
X2
Amin EE (z)) 2
Amiu (E(2,)) - ||| E[Z]]] = X2
=
2
2
By Lemma
13
di Σ
d2
1
P
Amin
Z
S
< P
Amin
Σ Z j=1
$ 2
Amiu (E(Zi))
d1
4
j=1
C2d Amin (E [E(
S n exe
- C2d11 A2
< n exp
2s
Since Z₁ 3 Zg for all j. for di 2
2a
log 2 this implies
U2A2
1
A2
C2d122
PP
Amin
Zj
<
S nexp
dj
2s
j=1
Se.
In other words,
d2
P
Amii
(m2) 2
> 1 -
25

---

C.3 Proof of Lemma
Lemma 5, Fix E Rdx= and ib E oV. For all 2 E R", (KZz, 2, 2) = |Topk 1l. Moreover,
Amia (K²)= = inf || |T 11
Proof. We compute
K 2, x) Eu
1 (6w"" (w') x))
| (w T x) = dS(w)
sg
(k( 2x))2 dS(w)
Vos vi(ww, x) (d dS(w)
Jsa- [w))( (
|Top211
which establishes the first part of the result. The second part of the result follows immediately by writing
Amin (K)) = inf (K 2, 2) || |T
inf
||
C.4 Proof of Lemma
Lemma 6. Suppose "1, En Sd-1 are 5-separated. Suppose that B E (0, and that R E Zzo
are such that N = Et= dim dim((H2 satisfies N C constant. Let g1."." ,9N be spherical harmonics which form an orthonormal basis of ① H H2r D NRNx defined as Dai - Ia (2;) then m (D)
( 84 (
(d-2))/2 where C > 0 is universal
7
Proof. Note that
n
2r B d
- 2r + (2++3))-3))
d-1 -
+ 3+ ++ -
N Σ
d 1
d-1
0=
Let us write D = [di,...
dn]. Fix k E [n] with + By addition formula
10
|
Ja (z,)²
R dim dim(F45--p))
yd (x,)2
R
dim (H
N.
26

---

By Lemma
13 and 8-separation, there exists constant C > 0 such that
kd dx) =
Σ Ia (2 (20k)
84
-(d-2)/4
(R + 3 + + 1/2
1) 111
$ C
d-1
84
-(d-2)/4
CN1/2
Suppose that
(8
-2d-2)/2
N 2 20
2
Observe that min (D) is the square root of the minimum eigenvalue of D D. By the Gershgorin circle theorem, the minimum eigenvalue D is at least
min (E
(DD ΣnD Dla
min En[n]
| 12
Eidd, dx)l
(id,, kegi
N
2
The result follows.
C.5 Proof of Lemma
Lemma 24, Let e E (0.1) and let 8 > 0. Suppose that T1,"! In E Sd-1 form a 8-separated
dataset. Let R E N be such that
1 2
2RR + d d-
84
2dd-2)/2
C
2
where is a universal constant. Then
(d + 1222/2211/2/ 3/2
i à
|T 2
(d R) 1/2
1/2 3/2
3/2
if = do
for all z E I² with ||||| < 1.
Proof. Let be the same constant as in Lemma and suppose that
d-1 1
8a 2
2dd22)/2
2
Let (0, 1} satisfy B when ā and when 1 do. Let N Ene dim dim (Hd
Note that
2r + d +
2r + +
3)
N =
Σ r=0
d
d-1
2R + d + 3 -11 1
d-1 1
2R + d-1
d-1 1
81
-(d-2)/2
2 C
2
27

---

Let 91,-1 .NN be spherical harmonics forming an orthonormal basis of + r== H2 1-
and let
B RN be the matrix defined by Bus gu (z.). By Lemma probability at least 1 - e. Since the functions are orthonormal,
d m ( (B) 2 with
NV.
1 Σ
(Tollx gall?
By Lemma 17 the above expression is equal to
dim (2)4s)
Ke Toga)?? Σ Σ
1i Th (2r+
By Lemmas 20 and 21
T 2r = c2r+9,a a2r+o,aY22+202 22 where c2r-B E R and
((5) (28-))
if ē
I( (
122+tedl 2
(15)
var (20-1)
if = v do.
r 2211
Hence
n dim (2r-1))
Tap 11 12
1224*3,0 Ku Y2r+
dim (Hg
min SS
(122++ 2)
1uz, Y2r+
N
min 05rsR
(102+ 2)
KHzx gu)12
min
(102++0,a)3 3)
24ga(x
USr5R
a=1 i=1
min
(102++ [z|l"
USrSR
min
(122+00,l 2) omial (m)
OSrSR
N
2
min
(102++0.013)
2
0S
So by
15
NT ( 28+1
if
2122 1
T 12
(16)
NoT (r( 28
if da.
d+ 284
We now separately analyze the cases where th and 10 = do.
Case 1: Ô. In this
(1) 2
22+1
Ta/2211 2 N
2
d+2R+1
(2R d d-1)
I (d 22+112
(2)
I ( 2
1(28 + d 11)
2
[2))(22++) +2)
r d+222+1
28

---

Then by Stirling's approximation,
|Tol 11 2 (2R 2R+d++1 (2
(d)
2R+1
2R
2
(2)
2
2) 2R--2
[d-2R+1
4+2R
--2
2 24++2 (2R+1
2R
(2R + 22R+2)-311 2)-
2R +
2 (d+ 2R + (2 2)
3/2
(d+ R)
Here the third inequality follows from the observations
2R -
0
2R
and
12R+1)
2R
2R
lim 11+000
lim
=e
2R+22
100000
2R +
Case 2: Vdl. In this case
dr (5) r (2R-1)2
| 2 N
r
1+22+1 2
d-1 -
(2
dl' (d) ( (2R-1)
2
r 0+2R+1
T(2R dd)
dT (d)
2 T 2R-1
(2 +
r d+2R+1
Then by Stirling's 's approximation,
(2R + 2R
ddd) e
(2R-1)
2R-2
e e22
1 dd-1/2e d(2 1)2041/22-2222 211
d+2R+1
d+2R
dd--R
2+2R
d+2R
(2R 1
28
2 (d+2R) 1/2
(2R
1) 1)-2(2R 1)1/2
d+ +1
12R
2 (d+ 1/2 122 3/2
d 2R
d+2R
2R -
d+ 2R +1
2R +
d+2R
2
28
(d+ 1/2
d 2R +1
2R +
2 (d + 1/2 R R-3/2 3/2
Hence we have established the desired bound on |TyMM in cases.
Lemma 7. Let d 2 3 and suppose that "1, En E gd-1 are 8-separated. For all z E R with |||||| < then
(1
(log(1/1)
82 is ò
T TT
log
(1g(1/)) log d
-3 81
if = vda.
Proof. We will consider multiple cases depending on the relative scaling of d and Let C be
-(d-2)/2
the same constant in Lemma 24 First suppose that d > C
4'
Let R = 1. Then
2R d-1
d
1) = 2
84
(d-2)/2
29

---

By Lemma 24
(T
2 in this case.
2)/2
Next suppose that 5
and Vdlog 2 (8 [og (1 + 16d) log z. Let
log((1 + C* + 2d logg(2200) log
R
(d 2)/2
84 2
Note that since <
we have
log(1 C)
2d lo1g//2/))
2d log(2/6)
2 1
log d
2-2 1og(2/8*)
2
and therefore
21og(1 + C*) + 4d 4dlog(2/0)
Vd
R <
<
log d
4
By definition,
log(1 1 + C) 2d log(2/0)
R>
log(d)
so that
2R + d 1
2R + d
d-1
2R
d
2R
2R
exp (2R(log(d) log(2R))
2 exp (2R (log(d) log (Vi)
exp (Rlog d)
2 exp(log(1 + C) + 2d (2/))
2d
2d/2)/2
Then by Lemma 24 the following bounds hold. If 1/: = o, then
1
2
(d + 1/22222 3/2
12
R 3/2
loog (1/0) log dl d 1oog(1//) logd d
-3/2
A2
8².
If àb Vdo, then
Tapuzl 2 2 (d+ 12 3/2
12
(d + 122
12 R R-3/2 3/2
+ dlog(2/0)
-3/2
log dl
log(n/e)
2 1
84
log d
30

---

Finally suppose that Vdlogd d
(8log(1 + C)
+
16d) log 2 and let R
(1 + 2C)d (3) [dd 1/1 Then
2(d 2(d-2)/(d-1)
2
R
5
(2)
2(d 23/(d11)
S s d)
8
2(d 2(d-2)/(d-1)
2
12
$ 1 vd
d log( (10)
2
2
2(d-2)/(d-1)
log(d)
8
d dlog(1/0) log(d) 8-2
and
2R+ 2 d-1
2R + d -
d-1
IV
d-1
d d-1
d-1
d
2C
d-1
2/(d-2)
1
d
20 1) 1)
2
2/(d-2)
2)
2
So by Lemma 24 the following bounds hold. If v = o, then
|2 2 2 (d 12)
2 (1 + d) 1/2 R1
d dlg( (10))
d dlog(1/0) -2
1+
82
log d
log
d dlog(1/0) log d
8².
If 1h Vdo, then
|70/4112 2 (d+ R)
1/2 3/2
2(d-2)/(d-1))
-1/2
2(d 2(d-2)/(a-1))
-3/2
2
22
d d+d d
/1/2
d
8
8
2(d-2)/(d-1)
-1/2
3(d-2)/
2
2
N 3/2
1+
②
-4(d-2)/(a-1
(1+ d) 3/2
d log(1 log(115)
84.
log
Hence we have shown the desired bound on [ 1I in all cases.
31

---

C.6 Upper bound on the minimum eigenvalue of the NTK
Our strategy to upper bound Amin (K) will be to prove that if two data points æ, x are close, then the Jacobian of the network does not separate points too much. We will need to find upper bounds for both |oo WWW x) (Ww') and (W=) +[ [l)
Lemma 25. Let e E (0, 1). Suppose that a; x' E gd-1 with I|e - x'll = 6. 1fdi S2 (log 2 then
with probability at least
(o( o (W 6
Proof. Note that (Wa))ooWW> can be written a sum of iid subexponential random variables:
de (((((w), x)) ((w,,
Since the entries of each w are iid standard Gaussian random variables and is 1-Lipschitz, (1 ((w,, m)) (any, x²) ))
| .z) (((nn) Il))
((w) x - x') 2')1
0².
Moreover,
[((o((w,, - o(w,, x1))) s [B[[ww - x') x²>
= || - x'1l 1|?
82.
So by Bernstein's inequality, for 20
P (lo (W 2212 52d, + t)
<(Wx')ll S P (lo(W)))o(WW'))))
s 2xxp
(-Cmin
d gz
where C' > 0 is a universal constant. Setting t = 6²dd with di 2 + log yields
(((l)(Wx)) -o (WW''|l 25) 2exp ( Cd1) S
This establishes the result.
Lemma 26. Suppose that x, x' E sd-1, If ~ N Ia). then
P(o((w, x)) + (w, x || x
Proof. Recall that for x' e sd-1
P(o((w, x)) + o((w, x²)))
where 0 is the angle formed by æ and x'; that is, 0 E [0, π with
cos (0) (x, x 1 マタ | x 2'1
By Taylor's theorem, 1 - cos(f) = g2 + ( so 1 - cos(O) x 02 for E [0, T). This implics
that 8² x || x'|l x2112, so x || - x' and therefore
(( x)) # ((w 2'1)) x || x'1
32

---

Lemma 27. e (0, 1). Suppose that x, E gd-1 with | - x'1 S 8. 1f d1
22 2 log )
then with probability least 1 6
- & vōd1.
Proof. Observe that
d1
o(Wx')1
4 > 23 = 4(8),
j=1
where Zy {0, 13 is equal to 1 if
0(100, x)) + ór (w,, x²))
and 0 otherwise, and S consists of the j [d1] such that Z, 1. The Z, are iid Bernoulli random
variables with parameter p, where p x 6 by Lemma 26 By Chernoff's s inequality (see Vershynin 2018 Theorem 2.3.1), for all t 2 dip
PP ([S) 2 5e dip (edip)
Then setting t ed1 p with d1
p log 4 yields
IP ([S) ed18) s ([S) 2 edip)
S ddv
4
By the lower bound of Chernoff's inequality, for all t S dip
edip
P(S) 51) Se Se-de dip
Then setting di2 with di 2
2 log 1 yields 2-28
P S S
dip
S exp
c
dip
2
< e
4
Therefore, with probability at least
2
d
S S ed18.
Let us denote this event by w. Observe that
| о (Ww) - @ 2
JES
and recall that uz AO0 1) for all j e [di]. By Bernstein's 's inequality, for all t t2
1 (000@Was (Wa) - u á ( 1 z |S| + 5) S 2exp (-C1 min x2
( ))
where C 0 is universal constant. Setting
|S| yields
P
v @ > 2 S
5) < 2exp(-C118))
33

---

Then
P
(10 0
- eddi
2 P O00 - 000 _ 2 <veedoo w)
2 P a 3 (( -
- 2 w)
A E P a O (( - WW)) 1 251s 5 1
E [[1
2 2xxp
(- T
01 d1d
w
- exx
P(w)
-c1 (ciee) )) (1-5)
w
2 exp
where we used that w is measurable with respect to S in the fourth line. So if d1 C,6
log then
P P(1ood(=))
2ved1
(1 - 2) (1 ;)
21-6.
Lemma 28. Suppose that a E 3d-1, If = Ω (log 2), then with probability at least 1 - 6,
a @ o(Wa)) x) i Vd..
Proof. Since a(ww,, x)) {0, 1) for all j [d1].
Σ
(30(( x))
j=l
d
j=1
Since the entries by are iid standard Gaussian random variables, Bernstein's 's inequality implies for all t 2 0
d
P([e @[])) di +
Σ
2 > di +
j=l
di ()
12
< 2 exp
- C min
-Omin
Setting & di with ? log 2 yields
P([| (WW))]l 2di) < 2exp(-Cdd.
Now we prove our main lemma which we will use relate the separation between data points the NTK.
Lemma 29. Let x, x' E gd-1 with ||e - æ'll 5 2. Lete e (0. ff 22 log 2). then with probability at least 1-c,
Vof((z) vof(=')1 v8.
34

---

Proof. By Lemma 27 if d1 2 log : then with probability at least 4
a @
W x E v ōd1.
Let us denote this event by w/. By Lemma 28 if dl 2 log + then with probability least 1 4
v w W Φ) x di.
Let us denote this event by w2. If both wi and w2 occur, then
[w)
Vw,
Vih (z
0z'll
vdi
+
[
olllr
Vd
(W(W))
||)|
--- I' +
0 (Wx) ooo ||a²1|
vd
ddz
V did
odi
vd
Vd
I Vo.
By Lemma
25 if di 2 log t, then with probability at least 1 - 2
[w. - Vw.f(x') = [z((())) fi('ll
26.
Let us denote this event by wa. wi, w2, and W3 oceur (which happens with probability least
1 t), then
E Vw, f(x) Vw. (V V f(e'
2 V8+0
S vo.
C.7 Proof of Theorem
Theorem 1. Let d 2 3, E (0,1), and 5. 8 (0, 22). Suppose that .,,... Fn E gd-1
5-separated and min;4k ||=;
x&ll I 8'. Define
[+ (log(1/8))
-3 log(d)
A
8²
If di 2 [ log n. then with probability at least
S Amin (K) S 8'.
Proof.
First prove the lower bound. Let A₁ be it is defined in Lemma 3 By Lemma 5
A inf
1
|=|==
Let
A = 1+ dlog(1/66 (1/8)
-3
82
log(d)
35

---

By Lemma 7 A1 such that if d1
2 C1 A for some constant C1 > 0. By Lemma
there exist constants C2. C3 > 0
X log then
P P(Amin ((Amin(KK)) < <Cad1) 5
(17)
Then for such d1.
P(Amin (Ki)
C3C₁A) 2 - 2
This establishes the lower bound.
Next prove the upper bound. Let k: [n] be two indices with o k such that || xx 8. di Z x log Z 5 log ! then by Lemma 29 there exists C4 > such that
((I))))( Vol( 2 C48') 2 2
Let us denote this event by w. If occurs, then
Amin (K) S (e, - ex) K(e; - ee)
[Vo[(x) (of(
88.
Hence, with probability at least 1 1 minimum eigenvalue. The two-sided bound then immediately follows from a union bound. n
5. Amin (K < 8' This establishes the upper bound for the
C.8 Uniform data sphere
Our main bounds for the smallest eigenvalue of the NTK are stated 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 lemmas which quantify the amount of separation data which uniformly distributed.
For (0, 1/2) and æ e sd-1, we define the spherical cap
Cap(æ, 8) {y sd-1 ly x1| S 8).
and the double spherical cap
DoubleCap(a. (x, 8) Cap(æ: 8) U Cap(Caa x, 8).
By Lemma 2.3 of Ball (199).
1 5 d-1
dS dS x 8))
2
(18)
2 2
We can also obtain a corresponding upper bound on the volume of a spherical cap.
Lemma 30. For 3d-1 and 1/2),
dS(Cap(æ, 8)) 4VT(CO)
d²
Here C' > 0 is universal constant.
Proof. For e E [0, n). let S. denote the set of all x'' E gd-1 such that the angle between æ and at at most é (that is, (ar, x²) 2 cos(ő)). The measure of S is given by
B(sin ( (d 1),2, 1/2)
B((d 1/2)
(see, e.g. Li 2010 Here the numerator refers to the incomplete beta function and the denominator refers to the beta function. We can bound
(i)
B sin (b);
(Ø);
d-
(d-33/2 - t) 11/2
2 2
sin (6)
(d-33//2
sin(d)a-1,
d
36

---

and
d - 1
(
d-1
(()
B
2
2
2-2
VT
2
I (2)
2VT
d d-2
The above two bounds imply
dS(S)) S 4 T sin (0)
4 TT sin(
AVT
(d l)(d 2) -
5
(19)
dc
d²
Now suppose that ø' Cap(ær, 6). Then | --- S 6, 1- x²) < 202. Let arccos (az, x²)) be the angle between x and x'. By Taylor's theorem, cos( 6) = 1 - for á E [0, n.. Thus
2 + + so cos( x 0²
28 1- (a, x') cos( (0) o²
So the angle between æ and x' at most Có for some universal constant C > -.. It follows that Cap(æ;, 5) Sca. Finally by (19
((CCp((x6)) < 4VT(C8)
d²
Since < 1. 2. the sets Cap(æ, 8) and Cap(- 8) are disjoint by the triangle inequality, Hence dS(DoubleCap(ar 6)) 2Cap(æ, 6)
and in particular by Lemma 30
dS (DoublccC,, 8)) S 4VT((08)
(20)
d²
for constant C' > O.
Lemma 31. Suppose that 2 2 and e E (0.1). If $1, In gd-1 are independent and uniformly distributed on 3d-1, then with probability least 6, the dataset is d-separated with 1/(d-1)
8
Proof. Let e [1,0,... "0' E gd-1 For each æ E gd-1, there exists an orthogonal matrix O such that 0, e. Note that for all gd-1 and [n]] O, x; Let i, le [n] with * Then for all 8 E (0, 1/2),
P([ 2x || < 5 or | 2p || S 8)
[|[P([|<; u < 8 or |00, æxl1 5 ax))
[[[P[|O,,, 8; - Fx
S 8 10,, x; + +0, xxll S 8 xx)]
[E[P([] v. ell < 8 10,, x + ell 8 xx)]
[|[[([a:: ell S 8 or ||x; +ell < ax)
IP[[| el < 8 or [ eel= < 8).
The expression on the final line is the measure of DoubleCap(e,. 8), and by
20 is bounded above by
4
d²
where C' > 0 is a constant. So
P([|,; æxll < 5 or [ xx |l < 8 for some i $ k) 1
Σ P([|. æıll - 8 or ||x xxll S 8)
4 2
<
d²
37

---

1/(d-1))
Setting 8 min
1.4 ede
we obtain
tVTn²
P([ æx ll S 5 or |2; + æ& 8 for some i + k) c.
Therefore, for this value of 6, the dataset is d-separated with probability at least 1 --e, c. To conclude, note that
1 co
1/(d-1)
1/(d-1)
C
4VTT2
n2
since
d
1/(d-1)
lim
=
d+000
4
Lemma 32. Suppose that 2 2 and e E (0, 1). If $1, Bn gd-1 are selected iid from
U(Sd-1), then with probability least 6, there exist i, [n]] with + such that
[lg((1/e) n2
1/(d-1)
| æull S
Proof. Let [1,0,... 1..0,....00) 00' gd-1, For each æ E sd-1, there exists an orthogonal matrix Oz such that O,æ - e. Note that for all gd-1 and i E [n]. On d æs Let k E [ni] with i of k. Then for all 8 E (0, 1/2),
P([| xxll 8)
E[P([| xx - 6 xx)]
E[P([] 32 O2, F&ll S x+
E[P([]O 8; ell < 6 ax)]
=E[P([1a: - el| S 8 ax)]
P(Ila; ell S 6).
The expression on the final line is the measure Cap(e, 8). and by Lemma 2.3 of Ball 1997)
is bounded below by (2) d-1 For each i E [m]. let wi denote the event that || ax 8 for
all j, k E [L. with o k. Trivially IP(n)) 1. If wi occurs for some i E [L, L]. then the
sets Cap(z;j 5/2) for j E [+] are disjoint. Indeed, if æ E Cap(2,,, 8/2) n Cap(xkk) 5/2), then by the
triangle inequality
8 8 2
| - æx ll S x =, + x - xx s
2
which contradicts wi. Now since these smaller spherical caps are disjoint, we can bound
ds ds (U)= E gd-1; | ---aa -xyy| 63) 2 as (U)= e g || æ, s 8/2))
= ds
8/2))
ds dS(Caa( 8/2))
d-1
2 Σ
2
3=1
i d-1
2
Since 2;41 is chosen independently from Ø1, .. Ø; this implies
P(w++1 wx) = PP [|[12
> Vj (w:)
d-1
i
< 1
2 4
38

---

By repeatedly conditioning we obtain
2( - æx
Vj. ks E [n]) = IP(wn)
(P(w)) II
Plwe -1. ww-i1)
2m
P((: wi-1)
1=2
d-1
<
2
2m
i
8
d-1)
exp
2 4
1=2
n² 0
d-1
I exp
2
4
Let us set min (,,4 log 2) 2)²11)
The above bounds imply that
P([ xxl 8 Vj,k E [n]) Se
so with probability at least - e, there exist i, E [na] such that || xxell S 8 with
1/(d-1)
8 85 n 200 1 - Corollary 2. Let 2 2 2, (0, 1), ..,
which is what we needed to show.
2n , US be mutually iid. Define
x= (1+ log(n/e)
2 1/(d-1)
log(d)
n+
df 2 (1+ n+log(1/e) log +. then with probability at least over the data and network parameters,
[log(1/))
1/(d-1)
À S Amin (K) S
n2
Proof.
By Lemma 14 with probability at least 1 i
X s [+ + log
Let us denote this event by W1. Let define
= min min (1 20 l alo; + 20k
#
and
8' = min
||: 2x
#
In particular, the dataset T1, Fn is 8- separatedd. By Lemma with probability least 4
1/(d-1)
8
Let us denote this event by wa. By Lemma
32
with probability least 1 /
log(1/e)
1/(d-1)
<
n²
39

---

Let us denote this event by wg. We condition on w1, w2, and wl for the remainder of the proof. Define
X (1+ dlog(1/0))
-3
8
log(d)
and
log(n/c) log(d)
c²
1/(d-1)
A (1+
n
note that
1 dlog (nn2 (o)2//)/(aa1))
-3
2/(d-1)
log(d)
log(n/e)
-3
1/(d-1)
(dg(
n2
X.
By Theorem 1 if
(
1 log(1/e)
log z x | 1| log (7)
1
di
d
then with probability at least 1 & over the network weights,
Amin (K) 2 X'
A
and
log(1/e) n
1/(d-1)
Amin K
8'
This is exactly the bound that we needed to show. By taking a union bound over all the favorable events, it follows that this event happens with probability at least 1 - e.
D Proof of Theorem g
D.1 Recap of the deep setting
Recall for the deep case consider fully connected networks with L layers and denote the layer widths with positive integers, do, ... dr. where do = d and d, = 1. For E [T. - 1] we define the
feature matrices Fi E IR X as
F (z)) f((x,))
For / E [L - 1] and æ E Rd we define the activation patterns Exxx) {0, 1]dexd to be the diagonal matrices
(x) (ii((((W
Lemma provides a useful decomposition the NTK.
Lemma 9. Let æ1.-.. En E Hdd be nonzero. There exists an open U C P of full Lebesgue measure such that f(x;)) is continuously differentiable on U for all E [n]. Moreover, for all f E U the NTK Gram matrix K defined in (T) with network function 7 satisfies
L-1
di
L-1 Fi)
II
K=
K-
(F
@
(Bin
where the ith row of B, E Ruxx is defined as
(xx))))
(IIkila) W/ En(e))))) W
lE 1], == L.
Bil.
1n
40

---

Proof. For any E [n], observe that f( )) is a PAP function Lee et al. 2020b Definition 5) and therefore f(x,,) differentiable almost everywhere (Lee al 2020b, Proposition 4). As the union of n null sets is also null set, we conclude that there exists open set U of full measure such that for all E [n] then f( () differentiable for any 0 E U.
0f denote the derivative of f with respect when it exists and be the minimum norm Let 80 uub-graddent otherwise. Using (Lee et al. 2020b] Corollary 13) then
1-1 K a.e. (0) T (F)
di II
2 2
L (F) (F)
00
80
OW;
OW,
where oW. E Rdih, 1x" By inspection, to prove the result claimed therefore suffices to show for any / E [4).0 E U and i,j E [r] that
(F)
(1:00))) OW.
0fr(m,
(fi-1
(1 fi-1 0)) (ils.))
(21)
aw.
First observe
(m.(m (f) = fi-1 (x; 0)0 fr (z; x
JW.. OW.
therefore establishing
21 for 1 = L. To establish (1) for l E [L. - 1], recall for k E [I - 1] that
Eg (z) diag (ō
(x))) and define (x) 1. Observe for S 1 < k k E [z] that
ff 0)
(x) 0f;-1 ()
(22)
oW:
aw.
while for 1: I.
(zx 0) (x) 3 fx=1 OW*
(23)
As result,
(. 0)
L-1+1
afi(;; 0)
Wz
II A=1
00,
oW.
L-++1
WE
II
(E((z) f1=1(=;0))
where the first equality arises from iterating (f,)); (z)
22 and the second by applying 23
Proceeding,
00: 00,
(fi-1(x;)² fi- f(-1 (
L-1
W E((as)) w )
T ((x(a))
L-1
(x;)))
II k=1+1
II k=1++1
W Ex(ss)))) W/
(x;- fi (2,)) (BBb))
as claimed.
D.2 Proof of Lemma 10
Lemma 33. Let z E Rdd be a fixed vector and W E Rgmd a random matrix with mutually iid
elements [W]s big NN(, for all i E [m]] and j E [d]. Consider the random vector y E R defined as (Wz) where denotes the ReLU function applied elementwise. For 8 E (0, 1) if
m Z 8-2 log(1/e then
P ((1 ()1 5) |1 S 11/1 (1+ |1=))) 21-c.
wT=
Proof. For i E [m] define Z, = T then Z, ~ NO0 1) are mutually iid. Let B, 1(2, > 0), note by symmetry B, ~ Ber(1 /2) furthermore these random variables for i E [n] are also mutually iid with respect to one another. As y/1 || B3 then
1 _ - ||| M
B,Z
41

---

For convenience let y' -//l:/ //|l=||am define S = f [n]]
B: 1}, then
1//1 11 Σ 2 x² ((S)).
EES
From
Lauurent & Massart
2000 Lemma 1) we have for any > 0
P
- (Sl) (11l'1
2 2v 2 (st) - exp(-(().
For 81 E (0,1) ) let / = | then
P ((1 -1)1SS & 11 & (1 + +1)] 2 1 exx (-
|S|6? (-19)6²
4
Observe
|S|
Di=1 Bi Bin(m, 1/2). With 02 (0, 1) then applying Hoeffding inequality
have
IP (1 62)
m
m
B₁ v (1 + 52) m
2 2exp
83m
2
i=1
Let denote the event that (1 (1-82) 82) 2
< |S| s (1 62) Ifm
16
log (/ee) then
8783(1 -22
P (1 - 61)(1 - 82) m
2 - =1++ + +52)
m7
2
2 P (1 (1- 81)(1 82) 2 $ |1 < (1+ 61) 52) 2 w P(W)
2 P (1-b1)|S}
$ ||'1l < (1+6:)15 | P(w)
(1162))8m ) (1 1 (1-2exp exp
83m
2 exp
8
2
2 (1-9) 9)
2 1 E.
For some ō E (0, let 82 81 6/3, then if m 19445-2 (2ogg44/ we have
P ((1 (1- 8) m
S 1 - (1 6) m
/)
N 1
2
from which the result claimed follows.
Lemma 10. Let x E gdo-1 12 2 and I E [L - 1). 1f dx 2 12 (og((1/e) ( for all l E [.] then
II da
II
dA
e-1
{1 se
W=1
1=1
holds with probability at least - e over the network parameters.
Proof. For i E [1] let wy denote the event that the inequality
2 (
(1- ; I
da S $11fx(<)111 < 1
1
dn
7
holds. We proceed by induction to establish that ((w.) 2 (1
y for all h E [1]. For the base case
note that fi (a:) = (W) and || = 1. Applying Lemma 33 with 5 = 1. if d1 2 12 log(1/c)
then IP(1) 2 1 5. Now suppose for & [ 1] that ((w)) (1 g Note
P(wk+1) P( ww (w)))(()>> P( wx) 3
Recall (x) = o(Wifu())) Conditioned wh. then again applying Lemma 33 with d = and dx+1 2 12 log(t/e) have
P( wx) 1 - f
which completes the proof of the induction hypothesis. As (1 - e/1)) 2 1- and S (1-1/11) < (1 + 1/t)' < then
dn
dn 2
12
Se
II 1=1
2
1=1
holds with probability at least
42

---

D.3 Proof of Lemma 34
Lemma 34, Let E Sdo-1, L 2 2 and assume de 2 Lo ( for all l [L 1). For any
I e [ 1] with probability at least 1 over the network parameters the following holds,
(z)) 2
II d2-
Proof. In what follows for convenience define empty product of scalars matrices as the scalar one. Let K E (I. 1). E [K], and for some arbitrary a E gdo-1 define
K
S E((x)
II
k=1+1
Let Wi,K denote the event
1 1 K 3/ 1
K
K
(TTT) T.
S S k
II k=1
2 dp
S2 2
(1+
1
(24)
suffices to lower bound the probability of the event w1 1- Let Fr denote the r-algebra generated by "", WK and note that Si, E FR. Let denote the event that fi( o 0, then
P(WI.I-1) 2 P(W Wr, (1,,,2))P(u,.---2
P( WI,L (P1L-)))((W,LL-2 WILL (M,L-3))P(aa PPW,LL-)))
P( w..))) P(Wz, (p)))
Fixing E (0, 1), our goal is to show each term in this product is at least (1 - 1,): indeed, if this is true then
() 1-1 1---)-12111 21-c
P(WI,1-1) 2 -
and our task is complete. To this end, first observe that as dg 2 L2 Log((L))) for all k E [L 1]. then P(1) > J. by Lemma 10 Proceeding to the term IP(rr, n), recall [Ex()]
((Wfi > 0). By symmetry the diagonal entries of Ex(x) are mutually iid Bernoulli random variables with parameter }. Therefore, using Hoeffding 's inequality for all 2 0
(1E
di
P
2
71
< 2 exx
2
dj
Let / d,, if di 2 log then with K 2 1, T. 2 2 follows that
K
1 K T.)
1
F(wi, mn) =
<
[x)
12 de
2
2
1
2
2
3
2 P
<
(x
E
(z:
11
2
di
2
(1 (Ex
di
2 1-
2
2
4
21 1 L
We now proceed to analyze P(W),,+ w1,a) for E 11, K - 1]. Note if wi, is true then |r > 0.
By definition this implies (x) > 0. however, if fa(x) = O then |>>(()) 0. Therefore wis being true implies (x) # For convenience in what follows we denote the jth column of
W as wy By definition
S St WT h+ (x))
43

---

therefore,
B B||
E [Fl]
Et W h+1 E Fil
d S || o((W8 fn(x))) Fn
E
As highlighted already, we condition on WI, then [n(x)) + and therefore the random variables (ō((w,, Jn (x))) are mutually iid Bernoulli random variables with parameter 2' Again by
symmetry ((w), Jn (x))) is independent of [| Therefore conditioned on w7,h
d
S S | ((o0. Fv
SL, 11? Fin
2
j=1
dp-1
|
2
j=1
dh+1
||St. 11?
2
Moreover, under the same conditioning
| 11? ((w1), fn fn()))))
- |||| St. 20,1
11
|| 1
S || 1
where the last line follows from Theorem 6.3.2 of Vershynin (018). As result, conditioned on wi, then using Bernstein's 's inequality (Vershynin such that for all /
2018 Theorem 2.8.1) there exists an absolute constant
TP
SLL+1
dn+1
2
FA
exp
(-emin
t2
2
da+il S
S
13
If dd+1
2L log 2L and
da-1
St then conditioning on Wi, we obtain
21.
P (11S
dx
dn+1
||
11:
St
Fn I
2L
As a result, for any E [t, K 1] we have P(WIn++1 wi,)) 2 1 i. from which the result claimed
follows.
D.4 Proof of Lemma 35
Lemma 35. Let x E 8do-1, L> 3 and assume dy da41 and dy Z Vlgg for all k [L- 1].
For any l E [L- - 1] with probability at least 1 c over the network parameters the following holds,
L-2
(x) <
II dx.
Proof. By Theorem 4.4.5 of Vershynin 20188 for any [L - 1] and all t 2
P W d( dd + +)) 2 1 - 2e -t
As d de 2 v log 21 then setting / Vlog? ? yields
P [Wall < 3C1 /d
2 P [W&l S C(Vdd-1 Vdb+th
c
2 1 L
44

---

Using union bound it follows that
P Wi S 30, ( d--1, Vd vk E IL 11-11) 21-6.
11)
Note that (x=)) S for all E [L. 1). therefore conditional on the above event we have
1-1
||
||
E((x)
I k=1+1
W Ex(
L-1
[x)]l
II ||>|||E
M=++1
L-1
W
k=1+1
L-2
dx.
k=1
To conclude we square both sides.
D.5 Proof of Lemma 11
Lemma 11. Let E S suppose L 2 3, d dx+1 for all k: E [L [L-1] and d,-1 2 2 log ( Then, for any I [L 1]. with probability at least the network parameters
(x)) x2
II de. k=1
Proof. Let Sdo-1 be arbitrary and recall Si(x) Ex)x)
(I
W.E, (x)) Also recall
that WT. E Rd is distributed as W (V(0s... ). Therefore by Vershynin 22018 6.3.2) for any A Rdexde-1 and 2 0
Theorem
(-
Ct²
P(J Z 112 - |||| 2 t) < 2
|
for some constant C > 0. As a result, with t 1 | then for some constant C' > 0
3 A
--
||A| A
A
AW l <
> 1 -xxp
Therefore, in order to lower bound suitable upper bound for S (z) 1/ and suitable lower bound for [[S,-1(2) [.. Let w denote event that both
| (z) W [1 with high probability suffices to condition on
|| = 2
dx
k=1
and
L-2
| <
d+
true. Combining Lemmas and 35 using union bound, then long L 3, dz d and
dy 2 L log aL for all & E [ 1] then P(w)) 5. As a result and also dz-1 2 24 log(2/e)
45

---

then
L-1
L-1
[
24-111111-11
dk
2 P
[|(()) =2
II dk P(w)
1 2 7 [x) - [| S 3
(
w P(w)
CC2 1I di
2 1 exp
P(W))
I di
2 1 exp
(-C2 dd.-1 P(w)
2 1 E
(1 (1-
2
2
2 -
as claimed.
D.6 Proof of Theorem 8
Theorem 8. Suppose (0,1/3), 5 (0, v2. do 2 3, the data 3, 22 ", E @do -1 is
5-separated and define
A = (1 do (0/((1)))))))))
-3
84
log do
With regard to the network architecture, let L 3, di 2 dit1 for all [L- di-1 2 2 log (7!) and d1 2 X log (x) log (2). Then with probability least over the network parameters
S Amin (K) S L.
Proof. Recall (8.
24-1
II
Amin
(FiF()
min
BBla.:11 s Amin (K) < 24-1
II
fl (f(z)))11|[
di
VE (x)
1=1
where the upper bound holds for any i [n). We start by analyzing the lower bound. Observe that F = (W,X)* o (WW has the same distribution as d, K2 in the shallow setting; see 3 Let
A2 be defined as Lemma
A do (Bu-u(3da-1) [o(u² X)T ou x)]) Amin 0000 vina
As the dataset 31, F2 ... nn ddo -1 is d-separated then by Lemma 7
do log(1/0) log do
A
+
84
Furthermore, d, 2 Xa log
log (2) then by Lemma
Az
Amin (F (F Z d1
with probability at least least 1 - f and as result
Amin FFF 2 di 11 log(n/c)
84
log(do)
with probability at least 1 - 5. Furthermore, as L 2 3, di 2 t4t for all I E [L 1] and
d--1 2 2t log (nn) then
|| 1 2-4 1-11 dx
min :E|n]
46

---

with probability at least
1' Via a union bound we conclude that the condition
1-11 26-1
log(n/e) log(dn)
-3
Ami (Fi (FIFY)
min [[ 11 2
8
di
sE(n
holds with probability at least construction that
4. Fixing some i [ni,, for the upper bound observe trivially by
[lfo(z)))
By assumption ds 2 I 1Plog(412 for all h [L 1]. With I [0, L 1] then by Lemma 10
(x; 2 2- ds
41. c holds with probability at least
Likewise by Lemma 34 for 1 E [2, L],
L-1
B. 212 (() W 2 14441
II dx
with probability at least
c 1L
Combining these via a union bound then for any E [ L 1).
T-1
[[( $2
II
d
k=1
holds with probability at least
2I Again using union bound now over the layers, it follows that
2--1
i
[fi(=:))1[[[Il $ L2
[
L-1
II
2
II d = (25)
L-1
de
with probability at least 1 5. As a result, using final union bound we conclude both the upper and lower bounds hold with probability at least
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state contributions in the introduction along with references to where we prove each of our results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss assumptions and include Limitations paragraph in our conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
48

---

Justification:
We precisely state our theorems and prove them in rigor in respective appen-
dices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
49

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuii wwwti//gguie///eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
50

---

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 96% CI, if the hypothesis of Normality of enrors 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 range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:://eeuis.eeeeeeeeee cwtpurrps.cpppliiep http://...c.......tttccccccclel.
Answer: [Yes]
Justification: None of the potential harms mentioned apply directly 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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
51

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee www.ree.wthcee....c... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
52

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "Ln6Tshdrj0", "reviewer": "Reviewer_NBnj", "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.", "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)\n* 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).\n* any idea on resolving the linear/quadratic gap?", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* widely distribution independent bounds\n* only standard assumptions\n* linear dependence on network width\n* extension to multilayer NN", "weaknesses": "* limited to ReLU activation\n* missing out some direct comparisons to previous bounds\n* study is motivated by NN optimization, but only the initialization phase is actually considered", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n> limited to ReLU activation\n\nWe 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.\n> missing out some direct comparisons to previous bounds\n\nIn 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).\n> study is motivated by NN optimization, but only the initialization phase is actually considered.\n\nTo 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. \n\n\n\nNext, in regard to the questions:\n\n> 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)\n\nThe 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. \n    \n> 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).\nany idea on resolving the linear/quadratic gap?\n\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KAUAkykWs1", "reviewer": "Reviewer_fqQK", "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.", "questions": "Please refer to weaknesses", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The bounds hold without requiring the distributional assumptions on the data and being applicable to high-dimensional settings. \n\n2. The authors introduce a novel application of the hemisphere transform and the addition formula for spherical harmonics, which serves as an innovative approach to analyzing the NTK. \n\n3. The results are applicable to both shallow and deep networks.", "weaknesses": "1. The current results are constrained to scenarios where the activation function is exclusively ReLU, which potentially limits the applicability. What is the primary impediment to generalizing the current results ? \n\n2. 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 ?\n\n3. Theorem 8 requires the layer width satisfy a pyramidal condition, I wonder whether modern DNNs architecture fullfills this requirement?\n\n4. 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.\n\nminors:\n$X \\in \\mathbb{R}^{d \\times n}$ should be $X \\in \\mathbb{R}^{d_0 \\times n}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> The current results are constrained to scenarios where the activation function is exclusively ReLU, which potentially limits the applicability\n\nWe 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.\n> 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\n\nWe 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.\n\n> Theorem 8 requires the layer width satisfy a pyramidal condition, I wonder whether modern DNNs architecture fulfills this requirement\n\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4LschNV9Ca", "reviewer": "Reviewer_k95g", "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.", "questions": "None", "limitations": "The authors have addressed the limitations of the work. This is a theoretical paper so the broader societal impact is negligible.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well written and provides a novel result that gives valuable insight into the behaviour of the NTK.", "weaknesses": "The major weaknesses of the paper are addressed by the authors and provide avenue for future research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rqkFFahuvf", "reviewer": "Reviewer_qjpA", "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.\n\nSpecifically, 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.\n\nThe 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.", "questions": "Main question:\n\nA 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. \n\nOther minor observations and questions:\n1) 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.\n\n 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}$. \n\n 3) Section 2 has a large overlap with the introduction. Could it be shortened or merged?\n\n4) 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.\n\n5) 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": "The main concerns were mentioned in the \"weaknesses\" part.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The studied problem is arguably relevant for dynamical study of NN evolution.\n\nThe techniques used are innovative within this field.", "weaknesses": "The main weakness is that requirement on the data distribution to be delta-separated is not as \"harmless\" or \"general\" as the authors claim (furthermore, I did not find a justification of this claim in the paper; the authors just state that $\\delta$-separation is \"milder\" than previous work requirements, without explaining why and without verifying that).\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n> 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).\n \nIn 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.\n\n> 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.  \n \nThere 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.\n\n> 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.\n\nThank 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].\n\n> 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\n\nThank you for highlighting this potential source of confusion, we will seek to rectify this point in future revisions of the paper.\n\n> 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}$.\n\nThanks for noting this typo. We will fix it in the final version.\n\n> Section 2 has a large overlap with the introduction. Could it be shortened or merged?\n\nThanks 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.\n\n\n> 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$\n affects the constant \n from Theorem 1.\n\nThe 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.\n\n> line 243-244 and lines 313-315: the fact that data are required to be \n$\\delta$-separated has to be mentioned, since it restricts generality.\n\nWe will clarify this point in the final version.\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ioRhwCFL5W", "reviewer": "Reviewer_Hffy", "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.", "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": "This paper is theoretical and limitations are stated clearly in the paragraphs (lines 317-320).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main significance of this paper is dropping the requirement of the input data dimension from [Nguyen2021] on the same topic, enabling more flexible application in other machine learning problems. The main result is presented with a clear step-by-step proof sketch.  \n\n\nReference:\n- *Quynh Nguyen, MarcoMondelli, and GuidoMontúfar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8119–8129. PMLR, 18–24 Jul 2021.*", "weaknesses": "I do not see any major weakness of this paper. It could be nicer if this paper also offers experimental results to support their calm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the positive feedback. In regard to your question,\n\n> 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,\n\nthis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)