Year: 2021

Abstract:
We study the dynamics of a neural network in function space when optimizing the mean squared error via gradient flow. We show that in the underparameterized regime the network learns eigenfunctions of an integral operator TK∞ determined by the Neural Tangent Kernel (NTK) at rates corresponding to their eigenvalues. For example, for uniformly distributed data on the sphere Sd−1 and rotation invariant weight distributions, the eigenfunctions of TK∞ are the spherical harmonics. Our results can be understood as describing a spectral bias in the underparameterized regime. The proofs use the concept of “Damped Deviations”, where deviations of the NTK matter less for eigendirections with large eigenvalues due to the occurence of a damping factor. Aside from the underparameterized regime, the damped deviations point-of-view can be used to track the dynamics of the empirical risk in the overparameterized setting, allowing us to extend certain results in the literature. We conclude that damped deviations offers a simple and unifying perspective of the dynamics when optimizing the squared error.

heading: 1 INTRODUCTION
text: A surprising but well established empirical fact is that neural networks optimized by gradient descent can find solutions to the empirical risk minimization (ERM) problem that generalize. This is surprising from an optimization point-of-view because the ERM problem induced by neural networks is nonconvex (Sontag & Sussmann, 1989; 1991) and can even be NP-Complete in certain cases (Blum & Rivest, 1993). Perhaps even more surprising is that the discovered solution can generalize even when the network is able to fit arbitrary labels (Zhang et al., 2017), rendering traditional complexity measures such as Rademacher complexity inadequate. How does deep learning succeed in the face of pathological behavior by the standards of classical optimization and statistical learning theory?
Towards addressing generalization, a modern line of thought that has emerged is that gradient descent performs implicit regularization, limiting the solutions one encounters in practice to a favorable subset of the model’s full capacity (see, e.g., Neyshabur et al., 2015; 2017; Gunasekar et al., 2017; Wu et al., 2017). An empirical observation is that neural networks optimized by gradient descent tend to fit the low frequencies of the target function first, and only pick up the higher frequencies later in training (Rahaman et al., 2019; Ronen et al., 2019; Basri et al., 2020; Xu et al., 2019). A closely related theme is gradient descent’s bias towards smoothness for regression problems (Williams et al., 2019; Jin & Montúfar, 2021). For classification problems, in suitable settings gradient descent provably selects max-margin solutions (Soudry et al., 2018; Ji & Telgarsky, 2019). Gradient descent is not impartial, thus understanding its bias is an important program in modern deep learning.
Generalization concerns aside, the fact that gradient descent can succeed in a nonconvex optimization landscape warrants attention on its own. A brilliant insight made by Jacot et al. (2018) is that in function space the neural network follows a kernel gradient descent with respect to the “Neural Tangent Kernel” (NTK). This kernel captures how the parameterization biases the trajectory in function space, an abstraction that allows one to largely ignore parameter space and its complications. This is a profitable point-of-view, but there is a caveat. The NTK still depends on the evolution of the network parameters throughout time, and thus is in general time-dependent and complicated to analyze. However, under appropriate scaling of the parameters in the infinite-width limit it remains constant (Jacot et al., 2018). Once the NTK matrix has small enough deviations to remain strictly positive definite throughout training, the optimization dynamics start to become comparable to that
of a linear model (Lee et al., 2019). For wide networks (quadratic or higher polynomial dependence on the number of training data samples n and other parameters) this property holds and this has been used by a variety of works to prove global convergence guarantees for the optimization (Du et al., 2019b; Oymak & Soltanolkotabi, 2020; Du et al., 2019a; Allen-Zhu et al., 2019a;b; Zou et al., 2020; Zou & Gu, 2019; Song & Yang, 2020; Dukler et al., 2020)1 and to characterize the solution throughout time (Arora et al., 2019; Basri et al., 2020). The NTK has been so heavily exploited in this setting that it has become synonymous with polynomially wide networks where the NTK is strictly positive definite throughout training. This begs the question, to what extent is the NTK informative outside this regime?
While the NTK has hitherto been associated with the heavily overparameterized regime, we demonstrate that refined analysis is possible in the underparameterized setting. Our theorems primarily concern a one-hidden layer network, however unlike many NTK results appearing in the literature our network has biases and both layers are trained. In fact, the machinery we build is strong enough to extend some existing results in the overparameterized regime appearing in the literature to the case of training both layers.

heading: 1.1 RELATED WORK
text: There has been a deluge of works on the Neural Tangent Kernel since it was introduced by Jacot et al. (2018), and thus we do our best to provide a partial list. Global convergence guarantees for the optimization, and to a lesser extent generalization, for networks polynomially wide in the number of training samples n and other parameters has been addressed in several works (Du et al., 2019b; Oymak & Soltanolkotabi, 2020; Du et al., 2019a; Allen-Zhu et al., 2019a;b; Zou et al., 2020; Zou & Gu, 2019; Song & Yang, 2020; Arora et al., 2019). To our knowledge, for the regression problem with arbitrary labels, quadratic overparameterization m & n2 is state-of-the art (Oymak & Soltanolkotabi, 2020; Song & Yang, 2020; Nguyen & Mondelli, 2020). E et al. (2020) gave a fairly comprehensive study of optimization and generalization of shallow networks trained under the standard parameterization. Under the standard parameterization, changes in the outer layer weights are more significant, whereas under the NTK parameterization both layers have roughly equal effect. Since we study the NTK parameterization in this work, we view the analysis as complementary.
Our work is perhaps most closely connected with Arora et al. (2019). In Theorem 4.1 in that work they showed that for a shallow network in the polynomially overparameterized regime m & n7, the training error along eigendirections of the NTK matrix decay linearly at rates that correspond to their eigenvalues. Our main Theorem 3.5 can be viewed as an analogous statement for the actual risk (not the empirical risk) in the underparameterized regime: eigenfunctions of the NTK integral operator TK∞ are approximately learned linearly at rates that correspond to their eigenvalues. In contrast with Arora et al. (2019), we have that the requirements on width m and number of samples n required to learn eigenfunctions with large eigenvalues are smaller compared to those with small eigenvalues. Surprisingly the machinery we build is also strong enough to prove in our setting the direct analog of Theorem 4.1. Note that Arora et al. (2019) train the hidden layer of a ReLU network via gradient descent, whereas we are training both layers with biases for a network with smooth activations via gradient flow. Due to the different settings, the results are not directly comparable. This important detail notwithstanding, our overparameterization requirement ignoring logarithmic factors is smaller by a factor of n 2
dδ4 where n is the number of input samples, d is the input dimension, and δ is the failure probability. Basri et al. (2020) extended Theorem 4.1 in Arora et al. (2019) to deep ReLU networks without bias where the first and last layer are fixed, with a higher overparameterization requirement than the original (Arora et al., 2019). Since the first and last layers are fixed this cannot be specialized to get a guarantee for training both layers of a shallow network even with ReLU activations.
Although it was not our focus, the tools to prove Theorem 3.5 are enough to prove analogs of Theorem 4 and Corollary 2 in the work of Su & Yang (2019). Theorem 4 and Corollary 2 of Su & Yang (2019) are empirical risk guarantees that show that for target functions that participate mostly in the top eigendirections of the NTK integral operator TK∞ , moderate overparameterization is possible. Again in this work they train the hidden layer of a ReLU network via gradient descent,
1Not all these works explicitly use that the NTK is positive definite. However, they all operate in the regime where the weights do not vary much and thus are typically associated with the NTK regime.
whereas we are training both layers with biases for a network with smooth activations via gradient flow. Again due to the different settings, we emphasize the results are not directly comparable. In our results the bounds and requirements are comparable to Su & Yang (2019), with neither appearing better. Nevertheless we think it is important to demonstrate that these results hold for training both layers with biases, and we hope our “Damped Deviations” approach will simplify the interpretation of the aforementioned works.
Cao et al. (2020, Theorem 4.2) provide an analogous statement to our Theorem 3.5 if you replace our quantities with their empirical counterparts. While our statement concerns the projections of the test residual onto the eigenfunctions of an operator associated with the Neural Tangent Kernel, their statement concerns the inner products of the empirical residual with those eigenfunctions. Their work was a crucial step towards explaining the spectral bias from gradient descent, however we view the difference between tracking the empirical quantities versus the actual quantities to be highly nontrivial. Another difference is they consider a ReLU network whereas we consider smooth activations; also they consider gradient descent versus we consider gradient flow. Due to the different settings we would like to emphasize that the scalings of the different parameters are not directly comparable, nevertheless the networks they consider are significantly wider. They require at least m ≥ Õ(max{σ−14k , −6}), where σk is a cutoff eigenvalue and is the error tolerance. By contrast in our work, to have the projection onto the top k eigenvectors be bounded by epsilon in L2 norm requires m = Ω̃(σ−4k −2). Another detail is their network has no bias whereas ours does.

heading: 1.2 OUR CONTRIBUTIONS
text: The key idea for our work is the concept of “Damped Deviatons”, the fact that for the squared error deviations of the NTK are softened by a damping factor, with large eigendirections being damped the most. This enables the following results.
• In Theorem 3.5 we characterize the bias of the neural network to learn the eigenfunctions of the integral operator TK∞ associated with the Neural Tangent Kernel (NTK) at rates proportional to the corresponding eigenvalues.
• In Theorem 3.7 we show that in the overparameterized setting the training error along different directions can be sharply characterized, showing that Theorem 4.1 in Arora et al. (2019) holds for smooth activations when training both layers with a smaller overparameterization requirement.
• In Theorem 3.8 and Corollary 3.9 we show that moderate overparameterization is sufficient for solving the ERM problem when the target function has a compact representation in terms of eigenfunctions of TK∞ . This extends the results in Su & Yang (2019) to the setting of training both layers with smooth activations.

heading: 2 GRADIENT DYNAMICS AND DAMPED DEVIATIONS

heading: 2.1 NOTATIONS
text: We will use ‖•‖2 and 〈•, •〉2 to denote the L2 norm and inner product respectively (for vectors or for functions depending on context). For a symmetric matrix A ∈ Rk×k, λi(A) denotes its ith largest eigenvalue, i.e. λ1(A) ≥ λ2(A) ≥ · · · ≥ λk(A). For a matrix A, ‖A‖op := sup‖x‖2≤1 ‖Ax‖2 is the operator norm induced by the Euclidean norm. We will let 〈•, •〉Rn denote the standard inner product on Rn normalized by 1n , namely 〈x, y〉Rn = 1 n 〈x, y〉2 = 1 n ∑n i=1 xiyi. We will let
‖x‖Rn = √ 〈x, x〉Rn be the associated norm. This normalized inner product has the convenient property that if v ∈ Rn such that vi = O(1) for each i then ‖v‖Rn = O(1), where by contrast ‖v‖2 = O( √ n). This is convenient as we will often consider what happens when n → ∞. ‖•‖∞ will denote the supremum norm with associated space L∞. We will use the standard big O and Ω notation with Õ and Ω̃ hiding logarithmic terms.

heading: 2.2 GRADIENT DYNAMICS AND THE NTK INTEGRAL OPERATOR
text: We will let f(x; θ) denote our neural network taking input x ∈ Rd and parameterized by θ ∈ Rp. The specific architecture of the network does not matter for the purposes of this section. Our training
data consists of n input-label pairs {(x1, y1), . . . , (xn, yn)} where xi ∈ Rd and yi ∈ R. We focus on the setting where the labels are generated from a fixed target function f∗, i.e. yi = f∗(xi). We will concatenate the labels into a label vector y ∈ Rn, i.e. yi = f∗(xi). We will let r̂(θ) ∈ Rn be the vector whose ith entry is equal to f(xi; θ)− f∗(xi). Hence r̂(θ) is the residual vector that measures the difference between our neural networks predictions and the labels. We will be concerned with optimizing the squared loss
Φ(θ) = 1
2n ‖r̂(θ)‖22 =
1 2 ‖r̂(θ)‖2Rn .
Optimization will be done by gradient flow
∂tθt = −∂θΦ(θ), which is the continuous time analog of gradient descent. We will denote the residual at time t, r̂(θt), as r̂t for the sake of brevity and similarly we will let ft(x) = f(x; θt). We will let rt(x) := ft(x)− f∗(x) denote the residual off of the training set for an arbitrary input x. We quickly recall some facts about the Neural Tangent Kernel and its connection to the gradient dynamics. For a comprehensive tutorial we suggest Jacot et al. (2018). The analytical NTK is the kernel given by
K∞(x, x′) := E [〈 ∂f(x; θ)
∂θ , ∂f(x′; θ) ∂θ 〉 2 ] ,
where the expectation is taken with respect to the parameter initialization for θ. We associate K∞ with the integral operator TK∞ : L2ρ(X)→ L2ρ(X) defined by
TK∞f(x) := ∫ X K∞(x, s)f(s)dρ(s),
where X is our input space with probability measure ρ. Our training data xi ∈ X are distributed according to this measure xi ∼ ρ. By Mercer’s theorem we can decompose
K∞(x, x′) = ∞∑ i=1 σiφi(x)φi(x ′),
where {φi}ni=1 is an orthonormal basis ofL2, {σi}∞i=1 is a nonincreasing sequence of positive values, and each φi is an eigenfunction of TK∞ with eigenvalue σi > 0. When X = Sd−1 is the unit sphere, ρ is the uniform distribution, and the weights of the network are from a rotation invariant distribution (e.g. standard Gaussian), {φi}∞i=1 are the spherical harmonics (which in d = 2 is the Fourier basis) due to K∞ being rotation-invariant (see Bullins et al., 2018, Theorem 2.2). We will let κ := maxx∈X K∞(x, x) which will be a relevant quantity in our later theorems. In our setting κ will always be finite as K∞ will be continuous and X will be bounded. The training data inputs {x1, . . . , xn} induce a discretization of the integral operator TK∞ , namely
Tnf(x) := 1
n n∑ i=1 K∞(x, xi)f(xi) = ∫ X K∞(x, s)f(s)dρn(s),
where ρn = 1n ∑n i=1 δxi is the empirical measure. We recall the definition of the time-dependent NTK2,
Kt(x, x ′) :=
〈 ∂f(x; θt)
∂θ , ∂f(x′; θt) ∂θ 〉 2 .
We can look at the version of Tn corresponding to Kt, namely
T tnf(x) := 1
n n∑ i=1 Kt(x, xi)f(xi) = ∫ X Kt(x, s)f(s)dρn(s).
We recall that the residual rt(x) := f(x; θ)− f∗(x) follows the update rule
∂trt(x) = − 1
n n∑ i=1 Kt(x, xi)rt(xi) = −T tnrt.
2The NTK is an overloaded term. To help ameliorate the confusion, we will use NTK to describe K∞ and NTK (italic font) to describe the time-dependent version Kt.
We will let (Ht)i,j := Kt(xi, xj) and H∞i,j := K ∞(xi, xj) denote the Gram matrices induced by these kernels and we will let Gt := 1nHt and G ∞ := 1nH
∞ be their normalized versions3. Throughout we will let u1, . . . , un denote the eigenvectors of G∞ with corresponding eigenvalues λ1, . . . , λn. The u1, . . . , un are chosen to be orthonormal with respect to the inner product 〈•, •〉Rn . When restricted to the training set we have the update rule
∂tr̂t = − 1
n Htr̂t = −Gtr̂t.

heading: 2.3 DAMPED DEVIATIONS
text: The concept of damped deviations comes from the very simple lemma that follows (the proof is provided in Appendix D). The lemma compares the dynamics of the residual r̂(t) on the training set to the dynamics of an arbitrary kernel regression exp(−Gt)r̂(0): Lemma 2.1. Let G ∈ Rn×n be an arbitrary positive semidefinite matrix and let Gs be the time dependent NTK matrix at time s. Then
r̂t = exp(−Gt)r̂0 + ∫ t
0
exp(−G(t− s))(G−Gs)r̂sds.
Let’s specialize the lemma to the case where G = G∞. In this case the first term is exp(−G∞t)r̂0, which is exactly the dynamics of the residual in the exact NTK regime when Gt = G∞ for all t. The second term is a correction term that weights the NTK deviations (G∞ −Gs) by the damping factor exp(−G∞(t−s)). We see that damping is largest along the large eigendirections ofG∞. The equation becomes most interpretable when projected along a specific eigenvector. Fix an eigenvector ui of G∞ corresponding to eigenvalue λi. Then the equation along this component becomes
〈r̂t, ui〉Rn = exp(−λit)〈r̂0, ui〉Rn + ∫ t
0
〈exp(−λi(t− s))(G∞ −Gs)r̂s, ui〉Rnds.
The first term above converges to zero at rate λi. The second term is a correction term that weights the deviatiations of the NTK matrix Gs from G∞ by the damping factor exp(−λi(t − s)). The second term can be upper bounded by∣∣∣∣∫ t
0
〈exp(−λi(t− s))(G∞ −Gs)r̂s, ui〉Rnds ∣∣∣∣ ≤ ∫ t
0
exp(−λi(t− s)) ‖G∞ −Gs‖op ‖r̂s‖Rn ds
≤ [1− exp(−λit)] λi sup s∈[0,t] ‖G∞ −Gs‖op ‖r̂0‖Rn ,
where we have used the property ‖r̂s‖Rn ≤ ‖r̂0‖Rn from gradient flow. When f∗ = O(1) we have that ‖r̂0‖Rn = O(1), thus whenever ‖G∞ −Gs‖op is small relative to λi this term is negligible. It has been identified that the NTK matrices tend to have a small number of outlier large eigenvalues and exhibit a low rank structure (Oymak et al., 2020; Arora et al., 2019). In light of this, the dependence of the above bound on the magnitude of λi is particularly interesting. We reach following important conclusion.
Observation 2.2. The dynamics in function space will be similar to the NTK regime dynamics along eigendirections whose eigenvalues are large relative to the deviations of the time-dependent NTK matrix from the analytical NTK matrix.
The equation in Lemma 2.1 concerns the residual restricted to the training set, but we will be interested in the residual for arbitrary inputs. Recall that rt(x) = f(x; θt)−f∗(x) denotes the residual at time t for an arbitrary input. Then more generally we have the following damped deviations lemma for the whole residual (proved in Appendix C.3).
3Gt and G∞ are the natural matrices to work with when working with the mean squared error as opposed to the unnormalized squared error. Also G∞’s spectra concentrates around the spectrum of the associated integral operator TK∞ and is thus a more convenient choice in our setting.
Lemma 2.3. Let K(x, x′) be an arbitrary continuous, symmetric, positive-definite kernel. Let [TKh](•) = ∫ X K(•, s)h(s)dρ(s) be the integral operator associated with K and let [T snh](•) = 1 n ∑n i=1Ks(•, xi)h(xi) denote the operator associated with the time-dependent NTK Ks. Then
rt = exp(−TKt)r0 + ∫ t
0
exp(−TK(t− s))(TK − T sn)rsds,
where the equality is in the L2 sense.
For our main results we will specialize the above lemma to the case whereK = K∞. However there are other natural kernels to compare against, say K0 or the kernel corresponding to some subset of parameters. We will elaborate further on this point after we introduce the main theorem. When specializing Lemma 2.3 to the caseK = K∞, we have that TK∞ and T sn are the operator analogs of G∞ and Gs respectively. From this statement the same concepts holds as before, the dynamics of rt will be similar to that of exp(−TK∞t)r0 along eigendirections whose eigenvalues are large relative to the deviations (TK∞ − T sn). In the underparameterized regime we can bound the second term and make it negligible (Theorem 3.5) and thus demonstrate that the eigenfunctions φi of TK∞ with eigenvalues σi will be learned at rate σi. When the input data are distributed uniformly on the sphere Sd−1 and the network weights are from a rotation-invariant distribution, the eigenfunctions of TK∞ are the spherical harmonics (which is the Fourier basis when d = 2). In this case the network is biased towards learning the spherical harmonics that correspond to large eigenvalues of TK∞ . It is in this vein that we will demonstrate a spectral bias.

heading: 3 MAIN RESULTS
text: Our theorems will concern the shallow neural network
f(x; θ) = 1√ m m∑ `=1 a`σ(〈w`, x〉2 + b`) + b0 = 1√ m aTσ(Wx+ b) + b0,
where W ∈ Rm×d, a, b ∈ Rm and b0 ∈ R and w` = W`,: denotes the `th row of W and σ : R→ R is applied entry-wise. θ = (aT , vec(W )T , bT , b0)T ∈ Rp where p = md + 2m + 1 is the total number of parameters. Here we are utilizing the NTK parameterization (Jacot et al., 2018). For a thorough analysis using the standard parameterization we suggest E et al. (2020). We will consider two parameter initialization schemes. The first initializes Wi,j(0) ∼ W , b`(0) ∼ B, a`(0) ∼ A, b0 ∼ B′ i.i.d., where W,B,A,B′ represent zero-mean unit variance subgaussian distributions. In the second initialization scheme we initialize the parameters according to the first scheme and then
perform the following swaps W (0) → [ W (0) W (0) ] , b(0) → [ b(0) b(0) ] , a(0) → [ a(0) −a(0) ] , b0 → 0 and
replace the 1√ m factor in the parameterization with 1√ 2m . This is called the “doubling trick” (Chizat et al., 2019; Zhang et al., 2020) and ensures that the network is identically zero f(x; θ0) ≡ 0 at initialization. We will explicitly state where we use the second scheme and otherwise will be using the first scheme.
The following assumptions will persist throughout the rest of the paper: Assumption 3.1. σ is a C2 function satisfying ‖σ′‖∞ , ‖σ′′‖∞ <∞. Assumption 3.2. The inputs satisfy ‖x‖2 ≤M .
The following assumptions will be used in most, but not all theorems. We will explicitly state when they apply. Assumption 3.3. The input domain X is compact with strictly positive Borel measure ρ. Assumption 3.4. TK∞ is strictly positive, i.e., 〈f, TK∞f〉2 > 0 for f 6= 0.
Most activation functions other than ReLU satisfy Assumption 3.1, such as Softplus σ(x) = ln(1 + ex), Sigmoid σ(x) = 11+e−x , and Tanh σ(x) = ex−e−x ex+e−x . Assumption 3.2 is a mild assumption which is satisfied for instance for RGB images and has been commonly used (Du et al., 2019b;a; Oymak & Soltanolkotabi, 2020). Assumption 3.3 is so that Mercer’s decomposition holds, which
is often assumed implicitly. Assumption 3.4 is again a mild assumption that is satisfied for a broad family of parameter initializations (e.g. Gaussian) anytime σ is not a polynomial function, as we will show in Appendix G. Assumption 3.4 is not strictly necessary but it simplifies the presentation by ensuring TK∞ has no zero eigenvalues.
We will track most constants that depend on parameters of our theorems such as M , the activation function σ, and the target function f∗. However, constants appearing in concentration inequalities such as Hoeffding’s or Bernstein’s inequality or constants arising from δ/2 or δ/3 arguments will not be tracked. We will reserve c, C > 0 for untracked constants whose precise meaning can vary from statement to statement. In the proofs in the appendix it will be explicit which constants are involved.

heading: 3.1 UNDERPARAMETERIZED REGIME
text: Our main result compares the dynamics of the residual rt(x) = f(x; θt) − f∗(x) to that of exp(−TK∞t)r0 in the underparameterized setting. Note that 〈exp(−TK∞t)r0, φi〉2 = exp(−σit)〈r0, φi〉2, thus exp(−TK∞t)r0 learns the eigenfunctions φi of TK∞ at rate σi. Therefore exp(−TK∞t)r0 exhibits a bias to learn the eigenfunctions of TK∞ corresponding to large eigenvalues more quickly. To our knowledge no one has been able to rigorously relate the dynamics in function space of the residual rt to exp(−TK∞t)r0, although that seems to be what is suggested by Ronen et al. (2019); Basri et al. (2020). The existing works we are aware of (Arora et al., 2019; Basri et al., 2020; Cao et al., 2020) characterize the bias of the empirical residual primarily in the heavily overparameterized regime (Cao et al. (2020) stands out as requiring wide but not necessarily overparameterized networks). By contrast, we characterize the bias of the whole residual in the underparameterized regime. Theorem 3.5. Assume that Assumptions 3.3 and 3.4 hold. Let Pk be the orthogonal projection in L2 onto span{φ1, . . . , φk} and let D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}. If we are doing the
doubling trick set S′ = 0 and otherwise set S′ = O (√ Õ(d) + log(c/δ) ) , S = ‖f∗‖∞ + S′.
Also let T > 0. Assumem ≥ D2 ‖y‖2Rn T 2, andm ≥ O(log(c/δ)+ Õ(d)) max { T 2, 1 } . Then with probability at least 1− δ we have that for all t ≤ T and k ∈ N
‖Pk(rt − exp(−TK∞t)r0)‖2 ≤ 1− exp(−σkt)
σk Õ
( S [1 + tS]
√ d√ m + S(1 + T ) √ p √ n ) and
‖rt − exp(−TK∞t)r0‖2 ≤ tÕ
( S [1 + tS]
√ d√ m + S(1 + T ) √ p √ n
) .
Theorem 3.5 will be proved in Appendix C. The proof uses the uniform deviation bounds for the NTK to bound Tn−T sn and tools from empirical process theory to show convergence of Tn to TK∞ uniformly over a class of functions corresponding to networks with bounded parameter norms.
To interpret the results, we observe that to track the dynamics for eigenfunctions corresponding to eigenvalue σk and above, the expression under the Õ needs to be small relative to 1σk . Thus the bias towards learning the eigenfunctions corresponding to large eigenvalues appears more pronounced. When t = log(‖r0‖2 / )/σk, we have that ‖Pk exp(−TK∞t)r0‖2 ≤ . Thus by applying this stopping time we get that to learn the eigenfunctions corresponding to eigenvalue σk and above up to accuracy we need t
2 √ m . and t 2√p√ n . which translates to m & σ−4k −2 and n &
pσ−4k −2. In typical NTK works the width m needs to be polynomially large relative to the number of samples n, where by contrast here the width depends on the inverse of the eigenvalues for the relevant components of the target function. From an approximation point-of-view this makes sense; the more complicated the target function the more expressive the model must be. We believe future works can adopt more precise requirements on the width m that do not require growth relative to the number of samples n. To further illustrate the scaling of the parameters required by Theorem 3.5, we can apply Theorem 3.5 for an appropriate stopping time to get a bound on the test error. Corollary 3.6. Assume Assumptions 3.3 and 3.4 hold. Suppose that f∗ = O(1) and assume we are performing the doubling trick where f0 ≡ 0 so that r0 = −f∗. Let k ∈ N and let Pk be
the orthogonal projection onto span{φ1, . . . , φk}. Set t = log( √ 2‖Pkf∗‖2/ 1/2)
σk Then we have that
m = Ω̃( d σ4k
) and n = Ω̃ (
p σ4k
) suffices to ensure with probability at least 1− δ
1 2 ‖rt‖22 ≤ 2 + 2 ‖(I − Pk)f ∗‖22 .
If one specialized to the case where f∗ is a finite sum of eigenfunctions of TK∞ (when the data is uniformly distributed on the sphere Sd−1 and the network weights are from a rotation invariant distribution this corresponds to a finite sum of spherical harmonics, which in d = 2 is equivalently a bandlimited function) one can choose k such that ‖(I − Pk)f∗‖22 = 0. It is interesting to note that in this special case gradient flow with early stopping achieves essentially the same rates with respect to m and n (up to constants and logarithms) as the estimated network in the classical approximation theory paper by Barron (1994). It is also interesting to note that the approximation results by Barron (1994) depend on the decay in frequency domain of the target function f∗ via their constant Cf∗ , and similarly for us the constant 1/σ4k grows with the bandwidth of the target function in the case of uniform distribution on the sphere S1 which we mentioned parenthetically above.
While in Theorem 3.5 we compared the dynamics of rt against that of exp(−TK∞t)r0, the damped deviations equation given by Lemma 2.3 enables you to compare against exp(−TKt)r0 for an arbitrary kernel K. There are other natural choices for K besides K = K∞, the most obvious being K = K0. In Appendix C.8 we prove a version of Theorem 3.5 whereK = K0 and θ0 is an arbitrary deterministic parameter initialization. This could be interesting in scenarios where the parameters are initialized from a pretrained network or one has a priori knowledge that informs the selection of θ0. One could let K be the kernel corresponding to some subset of parameters, such as the random feature kernel (Rahimi & Recht, 2008b) corresponding to the outer layer. This would compare the dynamics of training all layers to that of training a subset of the parameters. If one wanted to account for adaptations of the kernel Kt one could try to set K = Kt0 for some t0 > 0. However since θt0 depends on the training data it is not obvious how one could produce a bound for T s n − Kt0 . Nevertheless we leave the suggestion open as a possibility for future work.

heading: 3.2 OVERPARAMETERIZED REGIME
text: Once one has deviation bounds for the NTK so that the quantity ‖G∞ −Gs‖op is controlled, the damped deviations equation (Lemma 2.1) allows one to control the dynamics of the empirical risk. In this section we will demonstrate three such results that follow from this approach. The following is our analog of Theorem 4.1 from Arora et al. (2019) in our setting, proved in Appendix E. The result demonstrates that when the network is heavily overparameterized, the dynamics of the residual r̂t follow the NTK regime dynamics exp(−G∞t)r̂0. Theorem 3.7. Assume m = Ω̃(dn5 −2λn(H∞)−4) and m ≥ O(log(c/δ) + Õ(d)) and f∗ = O(1). Assume we are performing the doubling trick so that r̂0 = −y. Let v1, . . . , vn denote the eigenvectors of G∞ normalized to have unit L2 norm ‖vi‖2 = 1. Then with probability at least 1− δ r̂t = exp(−G∞t)(−y) + δ(t), where supt≥0 ‖δ(t)‖2 ≤ . In particular
‖r̂t‖2 = √√√√ n∑ i=1 exp(−2λit)|〈y, vi〉2|2 ± .
In the work of Arora et al. (2019) the requirement ism = Ω( n 7
λn(H∞)4κ2δ4 2 ) and κ = O( δ√ n ) where
w` ∼ N(0, κ2I) (not to be confused with our definition of κ := maxxK∞(x, x)). By contrast our weights have unit variance, which for Gaussian initialization corresponds to w` ∼ N(0, I). They require κ to be small to ensure the neural network is small in magnitude at initializeation. To achieve the same effect we can perform antisymmetric initializeation to ensure the network is equivalently 0 at initializeation. Our overparameterization requirement ignoring logarithmic factors is smaller by a factor of n 2
dδ4 . Again due to the different settings we do not claim superiority over this work.
The following is our analog of Theorem 4 by Su & Yang (2019) proved in Appendix F. This shows that when the target function has a compact representation in terms of eigenfunctions of TK∞ , a more moderate overparametrization is sufficient to approximately solve the ERM problem. Theorem 3.8. Assume Assumptions 3.3 and 3.4 hold. Furthermore assume m = Ω̃ ( −2dT 2 ‖f∗‖2∞ (1 + T ‖f∗‖∞)2 ) where T > 0 is a time parameter and m ≥ O(log(c/δ) + Õ(d)) and n ≥ 128κ 2 log(2/δ)
(σk−σk+1)2 . Also assume f ∗ ∈ L∞(X) ⊂ L2(X) and let PTK∞ be the or-
thogonal projection onto the eigenspaces of TK∞ corresponding to the eigenvalue α ∈ σ(TK∞) and higher. Assume that ∥∥(I − PTK∞ )f∗∥∥∞ ≤ ′ for some ′ ≥ 0. Pick k so that σk = α and σk+1 < α, i.e. k is the index of the last repeated eigenvalue corresponding to α in the ordered sequence {σi}i. Also assume we are performing the doubling trick so that r̂(0) = −y. Then we have with probability at least 1− 3δ over the sampling of x1, . . . , xn and θ0 that for t ≤ T
‖r̂t‖Rn ≤ exp(−λkt) ‖y‖Rn + 4κ ‖f∗‖2
√ 10 log(2/δ)
(σk − σk+1) √ n
+ 2 ′ + .
Su & Yang (2019) have ‖f∗‖2 ≤ ‖f∗‖∞ ≤ 1, κ ≤ 1 2 and they treat d as a constant. Taking these into account we do not see the overparameterization requirements or bounds of either work being superior to the other. From Theorem 3.8, setting = 4κ‖f ∗‖2 √ 10 log(2/δ)
(σk−σk+1) √ n and ′ = 0 we immediately get the analog of Corollary 2 in the work of Su & Yang (2019). This explains how in the special case that the target function is a finite sum of eigenfunctions of TK∞ , the width m and the number of samples n can grow at the same rate, up to logarithms, and still solve the ERM problem. This is an ERM guarantee for m = Ω̃(n) and thus attains moderate overparameterization. Corollary 3.9. Assume Assumptions 3.3 and 3.4 hold. Furhtermore assume m = Ω̃ ( n(σk−σk+1)2d‖f∗‖2∞(1+λ −1 k ‖f ∗‖∞) 2
κ2‖f∗‖22λ2k
) m ≥ O(log(c/δ) + Õ(d)) n ≥ 128κ
2 log(2/δ) (σk−σk+1)2 . Let
f∗, PTK∞ , and k be the same as in the hypothesis of Theorem 3.8. Furthermore assume that∥∥(I − PTK∞ )f∗∥∥∞ = 0. Also assume we are performing the doubling trick so that r̂(0) = −y. Set T = log( √ n ‖r̂(0)‖Rn)/λk. Then we have with probability at least 1− 3δ over the sampling of x1, . . . , xn and θ0 that for t ≤ T
‖r̂t‖Rn ≤ exp(−λkt) ‖y‖Rn + 8κ ‖f∗‖2
√ 10 log(2/δ)
(σk − σk+1) √ n
.
Note Su & Yang (2019) are training only the hidden layer of a ReLU network by gradient descent, by contrast we are training both layers with biases of a network with smooth activations by gradient flow. For Corollary 2 by Su & Yang (2019) they have the overparameterization requirement m & n log n ( 1 λ4k + log 4 n log2(1/δ) (λk−λk+1)2n2λ4k ) . Thus both bounds scale like n λ4k . Our bound has the extra factor (σk − σk+1)2 in front which could make it appear smaller at first glance but their Theorem 4 is strong enough to include this factor in the corollary they just chose not to. Thus we view both overparameterization requirements as comparable with neither superior to the other.

heading: 4 CONCLUSION AND FUTURE DIRECTIONS
text: The damped deviations equation allows one to compare the dynamics when optimizing the squared error to that of an arbitrary kernel regression. We showed how this simple equation can be used to track the dynamics of the test residual in the underparameterized regime and extend existing results in the overparameterized setting. In the underparameterized setting the neural network learns eigenfunctions of the integral operator TK∞ determined by the Neural Tangent Kernel at rates corresponding to their eigenvalues. In the overparameterized setting the damped deviations equation combined with NTK deviation bounds allows one to track the dynamics of the empirical risk. In this fashion we extended existing work to the setting of a network with smooth activations where all parameters are trained as in practice. We hope damped deviations offers a simple interpretation of the MSE dynamics and encourages others to compare against other kernels in future work.

heading: APPENDIX

heading: A ADDITIONAL NOTATIONS
text: We let [k] := {1, 2, 3, . . . , k}. For a set A we let |A| denote its cardinality. ‖•‖F denotes the Frobenius norm for matrices, and for two matricesA,B ∈ Rn×m we will let 〈A,B〉 = Tr(ATB) =∑n i=1 ∑m j=1Ai,jBi,j denote the Frobenius or entry-wise inner product. We will let BR := {x : ‖x‖2 ≤ R} to be the Euclidean ball of radius R > 0.

heading: B NTK DEVIATION AND PARAMETER NORM BOUNDS
text: Let Γ > 1. At the end of this section we will prove a high probability bound of the form
sup (x,x′)∈BM×BM
|Kt(x, x′)−K∞(x, x′)| = Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
Ideally we would like to use the results in Huang & Yau (2020) where they prove for a deep feedforward network without biases:
sup 1≤i,j≤n
|Kt(xi, xj)−K∞(xi, xj)| = Õ ( t2
m + 1√ m
) .
However there are three problems that prevent this. The first is that the have a constant under the Õ above that depends on the training data. Specifically their Assumption 2.2 requires that the smallest
singular value of the data matrix [xα1 , . . . , xαr ] is greater than cr > 0 where 1 ≤ α1, . . . , αr ≤ n are arbitrary distinct indices. As you send the number of samples to infinity you will have cr → 0, thus it is not clear how the bound will scale in the large sample regime. The second is that their bound only holds on the training data, whereas we need a bound that is uniform over all inputs. The final one is their network does not have biases. In the following section we will overcome these issues. The main difference between our argument and theirs is how we prove convergence at initialization. In their argument for convergence at initialization they make repeated use of a Gaussian conditioning lemma as they pass through the layers, and this relies on their Assumption 2.2. By contrast we will use Lipschitzness of the NTK and convergence over an net to prove convergence at initialization. As we see it, our deviation bounds for the time derivative ∂tKt are proved in a very similar fashion and the rest of the argument is very much inspired by their approach.
At the time of submission of this manuscript, we were made aware of the work by Liu et al. (2020) that provides an alternative uniform NTK deviation bound by providing a uniform bound on the operator norm of the Hessian. Their work is very nice, and it opens the door to extending the results of this paper to the other architectures they consider. Nevertheless, we proceed with our original analysis below.
This section is conceptually simple but technical. We will take care to outline the high level structure of each section to prevent the technicalities from obfuscating the overall simplicity of the approach. Our argument runs through the following steps:
• Control parameter norms throughout training. • Bound the Lipschitz constant of the NTK with respect to spatial inputs. • Use concentration of subexponential random variables (Bernstein’s inequality) to show that |K∞(z′) − K0(z′)| = Õ(1/ √ m) (roughly) for all z′ in an net of the spatial domain.
Combine with the Lipschitz property of the NTK to show convergence over all inputs, namely supz∈BM |K ∞(z)−K0(z)| = Õ(1/ √ m) (roughly).
• Produce the bound supz∈BM×BM |∂tKt(z)| = Õ(1/ √ m) (roughly). • Conclude that supz∈BM×BM |Kt(z)−K0(z)| = Õ(t/ √ m) (roughly).
B.1 IMPORTANT EQUATIONS
The following list contains the equations that are relevant for this section. We found it easier to read the following proofs by keeping these equations on a separate piece of paper or in a separate tab. We write a ⊗ x = axT . Also throughout this section the training data will be considered fixed and thus the randomness of the inputs is not relevant to this section. The randomness will come entirely from the parameter initialization θ0.
f(x; θ) = 1√ m aTσ(Wx+ b) + b0
x(1) := 1√ m σ(Wx+ b)
σ′1(x) := diag(σ ′(Wx+ b)) σ′′1 (x) := diag(σ ′′(Wx+ b))
∂af(x; θ) = 1√ m σ(Wx+ b) = x(1)
∂W f(x; θ) = 1√ m σ′1(x)a⊗ x
∂bf(x; θ) = 1√ m σ′1(x)a
∂b0f(x; θ) = 1
∂ta = − 1
n n∑ i=1 r̂ix (1) i
∂tW = − 1
n n∑ i=1 r̂i 1√ m σ′1(xi)a⊗ xi
∂tb = − 1
n n∑ i=1 r̂i 1√ m σ′1(xi)a
∂tb0 = − 1
n n∑ i=1 r̂i
∂tx (1) = ∂t 1√ m σ(Wx+ b) = 1√ m σ′1(x)[∂tWx+ ∂tb]
= − 1 n n∑ i=1 r̂i [ 1√ m σ′1(x)σ ′ 1(xi) a√ m ] [〈x, xi〉2 + 1]
∂tσ ′ 1(x) = ∂tσ ′(Wx+ b) = σ′′1 (x)diag(∂tWx+ ∂tb)
= − 1 n n∑ i=1 r̂i 1√ m σ′′1 (x)σ ′ 1(xi)diag(a)[〈x, xi〉2 + 1]

heading: B.2 A PRIORI PARAMETER NORM BOUNDS
text: In this section we will provide bounds for the following quantities:
ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1}
ξ̃(t) = max{max `∈[m] ‖w`(t)‖2 , ‖a(t)‖∞ , ‖b(t)‖∞ , 1}.
Here w` = W`,: ∈ Rd is the vector of input weights to the `th unit. These quantities appear repeatedly throughout the rest of the proofs of this section and thus need to be controlled. The parameter norm bounds will also be useful for the purpose of the covering number argument in Section C.6. This section is broken down as follows:
• Prove Lemma B.1 • Bound ξ(t)
• Bound ξ̃(t) The time derivatives throughout will repeatedly be of the form 1n ∑n i=1 r̂i(t)vi. Lemma B.1 provides a simple bound that we will use over and over again. Lemma B.1. Let ‖•‖ be any norm over a vector space V . Then for any v1, . . . , vn ∈ V we have∥∥∥∥∥ 1n n∑ i=1 r̂i(t)vi
∥∥∥∥∥ ≤ maxi∈[n] ‖vi‖ ‖r̂(t)‖Rn ≤ maxi∈[n] ‖vi‖ ‖r̂(0)‖Rn . Proof. Note that ∥∥∥∥∥ 1n n∑ i=1 r̂i(t)vi ∥∥∥∥∥ ≤ 1n n∑ i=1 |r̂i(t)| ‖vi‖ ≤ max i∈[n] ‖vi‖ 1 n n∑ i=1 |r̂i(t)|
≤ max i∈[n] ‖vi‖ 1√ n ‖r̂(t)‖2 = max i∈[n] ‖vi‖ ‖r̂(t)‖Rn ≤ max i∈[n] ‖vi‖ ‖r̂(0)‖Rn ,
where the last inequality follows from ‖r̂(t)‖Rn ≤ ‖r̂(0)‖Rn from gradient flow.
We now proceed to bound ξ(t).
Lemma B.2. Let ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1} and
D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1}.
Then for any initial conditions W (0), b(0), a(0) we have for all t ξ(t) ≤ exp ( D√ m ∫ t 0 ‖r̂(s)‖Rn ds ) ξ(0) ≤ exp ( D√ m ‖r̂(0)‖Rn t ) ξ(0).
Proof. Recall that
∂ta = − 1
n n∑ i=1 r̂ix (1) i
∂tW = − 1
n n∑ i=1 r̂i 1√ m σ′1(xi)a⊗ xi
∂tb = − 1
n n∑ i=1 r̂i 1√ m σ′1(xi)a.
We will show that each of the above derivatives is . ‖r̂(t)‖Rn ξ(t) then apply Grönwall’s inequality. By Lemma B.1 it suffices to show that the terms multiplied by r̂i in the above sums are . ξ(t). First we note that ∥∥∥x(1)i ∥∥∥
2 = ∥∥∥∥ 1√mσ(Wxi + b) ∥∥∥∥
2
≤ |σ(0)|+ 1√ m ‖σ′‖∞ ‖Wxi + b‖2
≤ |σ(0)|+ 1√ m ‖σ′‖∞
[ ‖W‖op ‖xi‖2 + ‖b‖2 ] ≤ |σ(0)|+ 1√
m ‖σ′‖∞
[ ‖W‖opM + ‖b‖2 ] ≤ Dξ.
Second we have that∥∥∥∥ 1√mσ′1(xi)a⊗ xi ∥∥∥∥ op = ∥∥∥∥ 1√mσ′1(xi)a ∥∥∥∥ 2 ‖xi‖2 ≤M ‖σ ′‖∞ 1√ m ‖a‖2 ≤ Dξ. Finally we have that ∥∥∥∥ 1√mσ′1(xi)a ∥∥∥∥ ≤ ‖σ′‖∞ 1√m ‖a‖2 ≤ Dξ.
Thus by Lemma B.1 and the above bounds we have
‖∂tW (t)‖op , ‖∂ta(t)‖2 , ‖∂tb(t)‖2 ≤ D ‖r̂(t)‖Rn ξ(t).
Let v(t) be a placeholder for one of the functions 1√ m a(t), 1√ m W (t), 1√ m b(t) with corresponding norm ‖•‖. Then we have that
‖v(t)‖ ≤ ‖v(0)‖+ ‖v(t)− v(0)‖ = ‖v(0)‖+ ∥∥∥∥∫ t
0
∂sv(s)ds ∥∥∥∥ ≤ ‖v(0)‖+
∫ t 0 ‖∂sv(s)‖ ds ≤ ξ(0) + ∫ t 0 ‖r̂(s)‖Rn√ m Dξ(s)ds.
This inequality holds for any of the three choices of v thus we get that ξ(t) ≤ ξ(0) + ∫ t
0
‖r̂(s)‖Rn√ m Dξ(s)ds.
Therefore by Grönwall’s inequality we get that ξ(t) ≤ exp ( D√ m ∫ t 0 ‖r̂(s)‖Rn ds ) ξ(0) ≤ exp ( D√ m ‖r̂(0)‖Rn t ) ξ(0).
We will now bound ˜ξ(t) using essentially the same argument as in the previous lemma.
Lemma B.3. Let ξ̃(t) = max{max`∈[m] ‖w`(t)‖2 , ‖a(t)‖∞ , ‖b(t)‖∞ , 1} and
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1}.
Then for any initial conditions W (0), b(0), a(0) we have for all t ξ̃(t) ≤ exp ( D√ m ∫ t 0 ‖r̂(s)‖Rn ds ) ξ̃(0) ≤ exp ( D√ m ‖r̂(0)‖Rn t ) ξ̃(0).
Proof. The proof is basically the same as Lemma B.2. We have that
∂tw` = − 1
n n∑ i=1 r̂i a`√ m σ′(〈w`, xi〉2 + b`)xi.
Now note ∥∥∥∥ a`√mσ′(〈w`, xi〉2 + b`)xi ∥∥∥∥
2
≤ 1√ m ‖a‖∞ ‖σ ′‖∞M ≤ D√ m ξ̃.
Thus by Lemma B.1 we have that
‖∂tw`(t)‖2 ≤ D√ m ‖r̂(t)‖Rn ξ̃(t).
On the other hand
∂ta = − 1
n n∑ i=1 r̂ix (1) i
with ∥∥∥x(1)i ∥∥∥∞ = ∥∥∥∥ 1√mσ(Wxi + b) ∥∥∥∥ ∞ ≤ 1√ m [|σ(0)|+ ‖σ′‖∞ ‖Wxi + b‖∞]
≤ 1√ m
[ |σ(0)|+ ‖σ′‖∞ (M max
` ‖w`‖2 + ‖b‖∞)
] ≤ D√
m ξ̃.
Thus again by Lemma B.1 we have
‖∂ta(t)‖∞ ≤ D√ m ‖r̂(t)‖Rn ξ̃(t).
Finally we have
∂tb = − 1
n n∑ i=1 r̂i 1√ m σ′1(xi)a
with ∥∥∥∥ 1√mσ′1(xi)a ∥∥∥∥ ∞ ≤ 1√ m ‖σ′‖∞ ‖a‖∞ ≤ D√ m ξ̃.
Again applying Lemma B.1 one last time we get
‖∂tb(t)‖∞ ≤ D√ m ‖r̂(t)‖Rn ξ̃(t).
Therefore by the same argument as in Lemma B.2 using Grönwall’s inequality we get that ξ̃(t) ≤ exp ( D√ m ∫ t 0 ‖r̂(s)‖Rn ds ) ξ̃(0) ≤ exp ( D√ m ‖r̂(0)‖Rn t ) ξ̃(0).
B.3 NTK IS LIPSCHITZ WITH RESPECT TO SPATIAL INPUTS
The NTK being Lipschitz with respect to spatial inputs is essential to our proof. The Lipschitz property means that to show convergence uniformly for all inputs it suffices to show convergence on an net of the spatial domain. Since the parameters are changing throughout time, the Lipschitz constant of the NTK will change throughout time. We will see that the Lipschitz constant depends on the quantities ξ(t) and ξ̃(t) from the previous Section B.2.
The NTK Kt(x, x′) is a sum of terms of the form g(x)T g(x′) where g is one of the derivatives ∂af(x; θt), ∂bf(x; θt), ∂W f(x; θt), ∂b0f(x; θt). Since ∂b0f(x; θt) ≡ 1 this term can be ignored for the rest of the section. The upcomming Lemma B.4 shows that if g is Lipschitz and bounded then (x, x′) 7→ g(x)T g(x′) is Lipschitz. This lemma guides the structure of this section:
• Prove Lemma B.4 • Show that ∂af(x; θ), ∂bf(x; θ), ∂W f(x; θ) are bounded and Lipschitz • Conclude the NTK is Lipschitz
Lemma B.4. Let g : Rk → Rl be L-Lipschitz with respect to the 2-norm, i.e. ‖g(x)− g(z)‖2 ≤ L ‖x− z‖2
and satisfy ‖g(x)‖2 ≤M for all x in some set X . Then Kg : X × X → R
Kg(x, x ′) := g(x)T g(x′)
is ML-Lipschitz with respect to the norm
‖(x, x′)‖ := ‖x‖2 + ‖x ′‖2 .
Proof. We have
|Kg(x, x′)−Kg(z, z′)| = |g(x)T g(x′)− g(z)T g(z′)| = |g(x)T (g(x′)− g(z′))|+ |(g(x)− g(z))T g(z′)|
≤ ‖g(x)‖2 ‖g(x ′)− g(z′)‖2 + ‖g(x)− g(z)‖2 ‖g(z ′)‖2 ≤ML ‖x′ − z′‖2 +ML ‖x− z‖2 ≤ML ‖(x, x ′)− (z, z′)‖ .
By the previous Lemma B.4, to show that the NTK is Lipschitz it suffices to show that ∂af(x; θ), ∂bf(x; θ), ∂W f(x; θ), ∂b0f(x; θ) are bounded and Lipschitz. The following lemma bounds the norms of the derivatives ∂af(x; θ), ∂W f(x; θ), ∂bf(x; θ). Lemma B.5. Let D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1} and
ξ = max{ 1√ m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2 , 1}.
Then ‖∂af(x; θ)‖2 , ‖∂W f(x; θ)‖F , ‖∂bf(x; θ)‖2 ≤ Dξ.
Proof. We have ‖∂af(x; θ)‖2 = ∥∥∥∥ 1√mσ(Wx+ b) ∥∥∥∥ 2 ≤ |σ(0)|+ 1√ m ‖σ′‖∞ ‖Wx+ b‖2
≤ |σ(0)|+ 1√ m ‖σ′‖∞
[ ‖W‖op ‖x‖2 + ‖b‖2 ] ≤ |σ(0)|+ 1√
m ‖σ′‖∞
[ ‖W‖opM + ‖b‖2 ] ≤ Dξ,
‖∂W f(x; θ)‖F = ∥∥∥∥ 1√mσ′1(x)a⊗ x ∥∥∥∥ F = ∥∥∥∥ 1√mσ′1(x)a ∥∥∥∥ 2 ‖x‖2 ≤ M√ m ‖σ′‖∞ ‖a‖2 ≤ Dξ,
‖∂bf(x; θ)‖2 = ∥∥∥∥ 1√mσ′1(x)a ∥∥∥∥ 2 ≤ 1√ m ‖σ′‖∞ ‖a‖2 ≤ Dξ.
The following lemma demonstrates that ∂af(x; θ), ∂W f(x; θ), and ∂bf(x; θ) are Lipschitz as functions of the input x. Lemma B.6. Let
ξ = max{ 1√ m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2 , 1},
ξ̃ = max{max `∈[m] ‖w`‖2 , ‖a‖∞ , ‖b‖∞ , 1},
D′ = max{‖σ′‖∞ ,M ‖σ ′′‖∞ , ‖σ ′′‖∞}, L = 2ξξ̃D′.
Then ∂af(x; θ), ∂bf(x; θ), ∂W f(x; θ) are all L-Lipschitz with respect to the Euclidean norm ‖•‖2. In symbols:
‖∂af(x; θ)− ∂af(y; θ)‖2 ≤ L ‖x− y‖2 ‖∂W f(x; θ)− ∂W f(y; θ)‖F ≤ L ‖x− y‖2 ‖∂bf(x; θ)− ∂bf(y; θ)‖2 ≤ L ‖x− y‖2 .
Proof. We have ‖∂af(x; θ)− ∂af(y; θ)‖2 = ∥∥∥∥ 1√m (σ(Wx+ b)− σ(Wy + b)) ∥∥∥∥ 2
≤ 1√ m ‖σ′‖∞ ‖W (x− y)‖2 ≤ 1√ m ‖σ′‖∞ ‖W‖op ‖x− y‖2 ≤ L ‖x− y‖2 ,
‖∂W f(x; θ)− ∂W f(y; θ)‖F = ∥∥∥∥ 1√mσ′1(x)a⊗ x− 1√mσ′1(y)a⊗ y ∥∥∥∥ F
≤ ∥∥∥∥ 1√mσ′1(x)a⊗ [x− y] ∥∥∥∥ F + ∥∥∥∥ 1√m [σ′1(x)a− σ′1(y)a]⊗ y ∥∥∥∥ F
≤ 1√ m ‖σ′1(x)a‖2 ‖x− y‖2 + 1√ m ‖[σ′1(x)− σ′1(y)]a‖2 ‖y‖2
≤ 1√ m ‖σ′‖∞ ‖a‖2 ‖x− y‖2 + 1√ m ‖σ′(Wx+ b)− σ′(Wy + b)‖∞ ‖a‖2M
≤ 1√ m ‖σ′‖∞ ‖a‖2 ‖x− y‖2 + 1√ m ‖σ′′‖∞ ‖W (x− y)‖∞ ‖a‖2M
≤ 1√ m ‖σ′‖∞ ‖a‖2 ‖x− y‖2 + 1√ m ‖σ′′‖∞ max `∈[m] ‖w`‖2 ‖x− y‖2 ‖a‖2M
≤ L ‖x− y‖2 ,
‖∂bf(x; θ)− ∂bf(y; θ)‖2 = ∥∥∥∥ 1√mσ′1(x)a− 1√mσ′1(y)a ∥∥∥∥ 2
≤ 1√ m ‖σ′(Wx+ b)− σ′(Wy + b)‖∞ ‖a‖2
≤ 1√ m ‖σ′′‖∞ ‖W (x− y)‖∞ ‖a‖2
≤ 1√ m ‖σ′′‖∞ max `∈[m] ‖w`‖2 ‖x− y‖2 ‖a‖2 ≤ L ‖x− y‖2 .
Finally we can prove that the Neural Tangent Kernel is Lipschitz. Theorem B.7. Consider the Neural Tangent Kernel K(x, y) = 〈∂af(x; θ), ∂af(y; θ)〉2 + 〈∂bf(x; θ), ∂bf(y; θ)〉2 + 〈∂W f(x; θ), ∂W f(y; θ)〉+ 1
and let ξ = max{ 1√
m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2 , 1},
ξ̃ = max{max `∈[m] ‖w`‖2 , ‖a‖∞ , ‖b‖∞ , 1},
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1},
D′ = max{‖σ′‖∞ ,M ‖σ ′′‖∞ , ‖σ ′′‖∞}. Then the Neural Tangent Kernel is Lipschitz with respect to the norm
‖(x, y)‖ := ‖x‖2 + ‖y‖2 with Lipschitz constant L := 6DD′ξ2ξ̃. In symbols:
|K(x, y)−K(x′, y′)| ≤ L ‖(x, y)− (x′, y′)‖ .
Proof. By Lemma B.5, we have that the gradients are bounded ‖∂af(x; θ)‖2 , ‖∂W f(x; θ)‖F , ‖∂bf(x; θ)‖2 ≤ Dξ. Also by Lemma B.6 the gradients are Lipschitz with Lipschitz constant 2ξξ̃D′. Thus these two facts combined with Lemma B.4 tell us that each of the three terms 〈∂af(x; θ), ∂af(y; θ)〉, 〈∂bf(x; θ), ∂bf(y; θ)〉, and 〈∂W f(x; θ), ∂W f(y; θ)〉 are individually Lipschitz with constant (Dξ) · (2ξξ̃D′). Thus the Lipschitz constant of the NTK itself is bounded by the sum of the 3 Lipschitz constants, for a total of 6DD′ξ2ξ̃.
Using that the NTK at time zero K0(x, y) is Lipschitz we can prove that the analytical NTK K∞ = E[K0(x, y)] is Lipschitz. We will use this primarily as a qualitative statement, meaning that the estimate that we derive for the Lipschitz constant will not be used as it is not very explicit. Rather, in theorems where we use the fact that K∞ is Lipschitz we will simply take the Lipschitz constant of K∞ as an external parameter. Theorem B.8. Assume that Wi,j(0) ∼ W , b`(0) ∼ B, a`(0) ∼ A are all i.i.d. zero-mean, unit variance subgaussian random variables. Let
ξ(0) = max{ 1√ m ‖W (0)‖op , 1√ m ‖b(0)‖2 , 1√ m ‖a(0)‖2 , 1},
ξ̃(0) = max{max `∈[m] ‖w`(0)‖2 , ‖a(0)‖∞ , ‖b(0)‖∞ , 1},
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1},
D′ = max{‖σ′‖∞ ,M ‖σ ′′‖∞ , ‖σ ′′‖∞}. Then the analytical Neural Tangent Kernel K∞(x, y) = E[K0(x, y)] is Lipschitz with respect to the norm ‖(x, y)‖ := ‖x‖2 + ‖y‖2 with Lipschitz constant ≤ 6DD′E[ξ2ξ̃] < ∞. If one instead does the doubling trick then the same conclusion holds.
Proof. First assume we are not doing the doubling trick. We note that |K∞(x, y)−K∞(x′, y′)| = |E[K0(x, y)]− E[K0(x′, y′)]| ≤ E |K0(x, y)−K0(x′, y′)| ≤ 6DD′E[ξ2ξ̃] ‖(x, y)− (x′, y′)‖
where the last line follows from the Lipschitzness of K0 provided by Theorem B.7. Using that ‖W (0)‖op ≤ ‖W (0)‖F and the fact that the Euclidean norm of a vector with i.i.d. subgaussian entries is subgaussian (Vershynin, 2018, Theorem 3.1.1), we have that ξ(0) and ξ̃(0) are maximums of subgaussian random variables. Since a maximum of subgaussian random variables is subgaussian, we have that ξ(0) and ξ̃(0) are subgaussian. From the inequality ab ≤ 12 (a
2 + b2) we get E[ξ2ξ̃] ≤ 12E[ξ 4] + 12E[ξ̃ 2] < ∞ since moments of subgaussian random variables are all finite. Since the doubling trick does not change the distribution of K0, the same conclusion holds under that initialization scheme.
B.4 NTK CONVERGENCE AT INITIALIZATION
In this section we prove that supz∈BM×BM |K0(z) −K ∞(z)| = Õ(1/
√ m). Our argument traces
the following steps:
• Show that K0 is sum of averages of m independent subexponential random variables • Use subexponential concentration to show that supz′∈∆ |K0(z′)−K∞(z′)| = Õ(1/ √ m)
for all z′ in an net ∆ of BM ×BM • Use that K0 is Lipschitz and convergence over the epsilon net ∆ to show that
sup z∈BM×BM
|K0(z)−K∞(z)| = Õ(1/ √ m) (roughly)
We recall the following definitions 2.5.6 and 2.7.5 from Vershynin (2018). Definition B.9. (Vershynin 2018) Let Y be a random variable. Then we define the subgaussian norm of Y to be
‖Y ‖ψ2 = inf{t > 0 : E exp(Y 2/t2) ≤ 2}
If ‖Y ‖ψ2 <∞, then we say Y is subgaussian. Definition B.10. (Vershynin 2018) Let Y be a random variable. Then we define the subexponential norm of Y to be ‖Y ‖ψ1 = inf{t > 0 : E exp(|Y |/t) ≤ 2} If ‖Y ‖ψ1 <∞, then we say Y is subexponential.
We also recall the following useful lemma Vershynin (2018, Lemma 2.7.7). Lemma B.11. (Vershynin 2018) Let X and Y be subgaussian random variables. Then XY is subexponential. Moreover
‖XY ‖ψ1 ≤ ‖X‖ψ2 ‖Y ‖ψ2
We recall one last definition Vershynin (2018, Definition 3.4.1) Definition B.12. (Vershynin 2018) A random vector Y ∈ Rk is called subgaussian if the one dimensional marginals 〈Y, x〉 are subgaussian random variables for all x ∈ Rk. The subgaussian norm of Y is defined as
‖Y ‖ψ2 = sup x∈Sk−1 ‖〈Y, x〉‖ψ2
The typical example of a subgaussian random vector is a random vector with independent subgaussian coordinates. The following lemma demonstrates that the NTK at initializeation is a sum of terms that are averages of independent subexponential random variables, which will enable us to use concentration arguments later. Theorem B.13. Let w`, b`, a` all be independent subgaussian random variables with subgaussian norms satisfying ‖•‖ψ2 ≤ K. Furthermore assume ‖1‖ψ2 ≤ K. Also let
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1}.
Then for fixed x, y, each of the following
〈∂af(x; θ), ∂af(y; θ)〉, 〈∂bf(x; θ), ∂bf(y; θ)〉, 〈∂W f(x; θ), ∂W f(y; θ)〉
is an average of m independent subexponential random variables with subexponential norms bounded by D2K2.
Proof. We first observe that
〈∂af(x; θ), ∂af(y; θ)〉2 = 1
m 〈σ(Wx+ b), σ(Wy + b)〉2
= 1
m m∑ `=1 σ(〈w`, x〉2 + b`)σ(〈w`, y〉2 + b`),
〈∂bf(x; θ), ∂bf(y; θ)〉2 = 〈 1√ m σ′1(x)a, 1√ m σ′1(y)a〉2
= 1
m m∑ `=1 a2`σ ′(〈w`, x〉2 + b`)σ′(〈w`, y〉2 + b`),
〈∂W f(x; θ), ∂W f(y; θ)〉 = 〈 1√ m σ′1(x)a⊗ x, 1√ m σ′1(y)a⊗ y〉2
= 1
m 〈σ′1(x)a, σ′1(y)a〉2〈x, y〉2 = 〈x, y〉2 m m∑ `=1 a2`σ ′(〈w`, x〉2 + b`)σ′(〈w`, y〉2 + b`).
Note that |σ(〈w`, x〉2 + b`)| ≤ |σ(0)|+ ‖σ′‖∞ [|〈w`, x〉|+ |b`|].
Thus
‖σ(〈w`, x〉2 + b`)‖ψ2 ≤ |σ(0)| ‖1‖ψ2 + ‖σ ′‖∞ [‖|〈w`, x〉|‖ψ2 + ‖|b`|‖ψ2 ]
≤ |σ(0)| ‖1‖ψ2 + ‖σ ′‖∞ [M ‖w`‖ψ2 + ‖|b`|‖ψ2 ]
≤ 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞}K ≤ DK.
Also |a`σ′(〈w`, x〉2 + b`)| ≤ |a`| ‖σ′‖∞ ≤ D|a`|,
therefore ‖a`σ′(〈w`, x〉2 + b`)‖ψ2 ≤ D ‖a`‖ψ2 ≤ DK. Finally ∥∥∥|〈x, y〉2|1/2a`σ′(〈w`, x〉2 + b`)∥∥∥ ψ2 ≤M ‖σ′‖∞ ‖a`‖ψ2 ≤ DK.
It follows by Lemma B.11 that each of 〈∂af(x; θ), ∂af(y; θ)〉, 〈∂W f(x; θ), ∂W f(y; θ)〉, and 〈∂bf(x; θ), ∂bf(y; θ)〉 is an average of m independent subexponential random variables with subexponential norm ‖•‖ψ1 ≤ D 2K2.
We now recall the following Theorem from Vershynin (2012, Theorem 5.39) which will be useful. Lemma B.14 (Vershynin 2012). LetA be anN×nmatrix whose rowsAi are independent subgaussian isotropic random vectors in Rn. Then for every t ≥ 0, with probability at least 1−2 exp(−ct2) one has the following bounds on the singular values
√ N − C √ n− t ≤ smin(A) ≤ smax(A) ≤ √ N + C √ n+ t.
Here C = CK > 0 depends only on the subgaussian norms K = maxi ‖Ai‖ψ2 of the rows.
Also the following special case of Vershynin (2012, Lemma 5.5) will be useful for us. Lemma B.15 (Vershynin 2012). Let Y be subgaussian. Then
P (|Y | > t) ≤ C exp(−ct2/ ‖Y ‖2ψ2).
It will be useful to remind the reader that C, c > 0 denote absolute constants whose meaning will vary from statement-to-statement, as this abuse of notation becomes especially prevalent during the concentration of measure arguments of the rest of the section. The following lemma provides a concentration inequality for the maximum of subgaussian random variables which will be useful for bounding ξ and ξ̃ later which is necessary for bounding the Lipschitz constant of K0. Lemma B.16. Let Y1, . . . , Yn be subgaussian random variables with ‖Yi‖ψ2 ≤ K for i ∈ [n]. Then there exists absolute constants c, c′, C > 0 such that
P (
max i∈[n] |Yi| > t+K
√ c′ log n ) ≤ C exp(−ct2/K2).
Proof. Since each Yi is subgaussian we have for any t ≥ 0 (Lemma B.15) P (|Yi| > t) ≤ C exp ( −ct2/ ‖Yi‖2ψ2 ) .
By the union bound, P (
max i∈[n] |Yi| > t+K
√ c−1 log n ) ≤ n∑ i=1 P ( |Yi| > t+K √ c−1 log n ) ≤ nC exp ( −c [ t+K √ c−1 log n ]2 /K2 ) = C exp(−ct2/K2).
Thus by setting c′ := c−1 we get the desired result.
We now introduce a high probability bound for ξ.
Lemma B.17. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let
ξ = max{ 1√ m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2}
Then with probability at least 1− δ
ξ ≤ 1 + C √ d+K2 √ log(c/δ)√
m
Proof. Note that by setting t = √ c−1 log(2/δ) in Lemma B.14 we have that with probability at least 1− δ 1√ m ‖W‖op ≤ 1 + C √ d√ m + √ c−1 log(2/δ)√ m
Also by Theorem 3.1.1 in (Vershynin, 2018)∥∥‖a‖2 −√m∥∥ψ2 ≤ CK2∥∥‖b‖2 −√m∥∥ψ2 ≤ CK2 Thus by Lemma B.15 and a union bound we have with probability at least 1− 2δ
1√ m ‖a‖2 , 1√ m ‖b‖2 ≤ 1 + C√ m K2 √ log(c/δ)
Thus by replacing every δ in the above arguments with δ/3 and using the union bound we have with probability at least 1− δ
ξ ≤ 1 + C √ d+K2 √ log(c/δ)√
m .
Similarly we now introduce a high probability bound for ξ̃.
Lemma B.18. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let
ξ̃ = max{max `∈[m] ‖w`‖2 , ‖a‖∞ , ‖b‖∞}
Then with probability at least 1− δ we have
ξ̃ ≤ √ d+ CK2 [√ log(c/δ) + √ logm ]
Proof. By Theorem 3.1.1 in (Vershynin, 2018) we have∥∥∥‖w`‖2 −√d∥∥∥ ψ2 ≤ CK2
Well then by Lemma B.16 there is a constant c′ > 0 so that P (
max `∈[m]
‖w`‖2 − √ d > t+ CK2 √ c′ logm ) ≤ P ( max `∈[m]
∣∣∣‖w`‖2 −√d∣∣∣ > t+ CK2√c′ logm) ≤ C exp(−ct2/K4). Thus by setting t = CK2 √ log(c/δ) we have with probability at least 1− δ
max `∈[m]
‖w`‖2 ≤ √ d+ CK2 √ log(c/δ) + CK2 √ logm
where we have absorbed the constant √ c′ into C. Similarly by Lemma B.16 and a union bound we get with probability at least 1− 2δ that
‖a‖∞ , ‖b‖∞ ≤ CK √ log(c/δ) + CK √ logm
Thus by replacing each δ with δ/3 in the above arguments and using the union bound we get with probability at least 1− δ
ξ̃ ≤ √ d+ CK2 [√ log(c/δ) + √ logm ]
We are now finally ready to prove the main theorem of this section. Theorem B.19. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1},
D′ = max{‖σ′‖∞ ,M ‖σ ′′‖∞ , ‖σ ′′‖∞}. Define
ρ(M,σ, d,K, δ,m) :=
CDD′ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 {√ d+ CK2 [√ log(c/δ) + √ logm ]} .
Let L(K∞) denote the Lipschitz constant of K∞. If
m ≥ C[log(c/δ) + 2d log(CM max{ρ, L(K∞)} √ m)],
then with probability at least 1− δ
sup z∈BM×BM |K0(z)−K∞(z)| ≤ 1√ m
[ 1 + CD2K2 √ log(c/δ) + 2d log(CM max{ρ, L(K∞)} √ m) ] .
If one instead does the doubling trick then the same conclusion holds.
Proof. First assume we are not doing the doubling trick. Recall that by Theorem B.7 that K0 is Lipschitz with constant at most
CDD′ξ(0)2 ˜ξ(0),
where ξ and ξ̃ are defined as in the theorem. Well then by Lemmas B.17, B.18 and a union bound we have with probability at least 1− 2δ
ξ(0)2ξ̃(0) ≤ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 {√ d+ CK2 [√ log(c/δ) + √ logm ]} .
Let L(K0), L(K∞) denote the Lipschitz constant of K0 and K∞ respectively. Then assuming the above inequality holds we have that
L(K0) ≤ ρ(M,σ, d,K, δ,m). (1) For conciseness from now on we will suppress the arguments of ρ. Now set
γ := 1
2 max{ρ, L(K∞)} √ m .
LetNγ(BM ) be the cardinality of a maximal γ-net of the ball BM = {x : ‖x‖2 ≤M} with respect to the L2 norm ‖•‖2. By a standard volume argument we have that
Nγ(BM ) ≤ ( CM
γ
)d .
By taking the product of two γ/2 nets of BM it follows that we can choose a γ net of BM × BM , say ∆, with respect to the norm ‖(x, y)‖ = ‖x‖2 + ‖y‖2 such that
|∆| ≤ ∣∣Nγ/2(BM )∣∣2 ≤ (CM
γ
)2d =:Mγ .
By Theorem B.13 for (x, y) ∈ BM ×BM fixed each of the following 〈∂af(x; θ), ∂af(y; θ)〉2, 〈∂bf(x; θ), ∂bf(y; θ)〉2, 〈∂W f(x; θ), ∂W f(y; θ)〉 is an average of m subexponential random variables with subexponential norm at most D2K2. Therefore separately from the randomness discussed before by Bernstein’s inequality Vershynin (2018, Theorem 2.8.1) and a union bound we have
P(|K0(x, y)−K∞(x, y)| > t) ≤ 3× 2 exp ( −cmin { mt2
D4K4 , mt D2K2
}) .
Thus for t ≤ D2K2 we have P(|K0(x, y)−K∞(x, y)| > t) ≤ 6 exp ( −c mt 2
D4K4
) .
Then by a union bound and the previous inequality we have that for t ≤ D2K2 P (
max z′∈∆
|K0(z′)−K∞(z′)| > t ) ≤ 6Mγ exp ( −c mt 2
D4K4
) .
Thus by setting t = CD2K2 √
log(c/δ)+logMγ√ m
(note that the condition on m in the hypothesis ensures that t ≤ D2K2) we get that with probability 1− δ
max z′∈∆
|K0(z′)−K∞(z′)| ≤ t.
Now fix z ∈ BM ×BM and choose z′ ∈ ∆ such that ‖z − z′‖ ≤ γ. Then |K0(z)−K∞(z)| ≤ |K0(z)−K0(z′)|
+ |K0(z′)−K∞(z′)|+ |K∞(z′)−K∞(z)| ≤ 2 max{L(K0), L(K∞)}γ + t. (2)
Note that this argument runs through for any z ∈ BM ×BM therefore sup
z∈BM×BM |K0(z)−K∞(z)| ≤ 2 max{L(K0), L(K∞)}γ + t.
Well by replacing δ with δ/3 in the previous arguments by taking a union bound we can assume that equations (1) and (2) hold simultaneously. In which case
sup z∈BM×BM
|K0(z)−K∞(z)| ≤ 2 max{L(K0), L(K∞)}γ + t ≤ 2 max{ρ, L(K∞)}γ + t
≤ 1√ m
+ CD2K2 √
log(c/δ) + logMγ√ m = 1√ m
+ CD2K2 √
log(c/δ) + 2d log(CM/γ)√ m
= 1√ m
[ 1 + CD2K2 √ log(c/δ) + 2d log(CM max{ρ, L(K∞)} √ m) ] ,
where we have used the definition ofMγ in the second-to-last equality and the definition of γ in the last equality. Since the doubling trick does not change the distribution of K0, the same conclusion holds under that initialization scheme.
We immediately get the following corollary. Corollary B.20. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Then
m ≥ C[log(c/δ) + Õ(d)] suffices to ensure that with probability at least 1− δ
sup z∈BM×BM
|K0(z)−K∞(z)| = Õ ( √ d√ m ) .
If one instead does the doubling trick then the same conclusion holds.

heading: B.5 CONTROL OF NETWORK AT INITIALIZATION
text: Many of our previous results depend on the quantity ‖r̂(0)‖Rn which depends on the network at initialization. Before we proceed we must control the infinity norm of the network at initialization and work out a few consequences of this. The following lemma controls ‖f(•; θ0)‖∞. Lemma B.21. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A, b0 ∼ B′ are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1}
L(m,σ, d,K, δ) := √ m ‖σ′‖∞ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 .
Assume that m ≥ C[log(c/δ) + d log(CML)].
Then with probability at least 1− δ
sup x∈BM
|f(x; θ0)| ≤ CDK2 √ d log(CML) + log(c/δ) = Õ( √ d).
Proof. First we note that∣∣∣∣ aT√mσ(Wx+ b)− aT√mσ(Wy + b) ∣∣∣∣ ≤ ‖a‖2√m ‖σ(Wx+ b)− σ(Wy + b)‖2
≤ ‖a‖2√ m ‖σ′‖∞ ‖W (x− y)‖2 ≤ ‖a‖2√ m ‖σ′‖∞ ‖W‖op ‖x− y‖2 ≤ √ m ‖σ′‖∞ ξ(0) 2 ‖x− y‖2 ,
where ξ(0) is defined as in Lemma B.17. Thus f(•; θ0) is Lipschitz with constant L =√ m ‖σ′‖∞ ξ(0)2. Well then by Lemma B.17 we have with probability at least 1− δ
ξ(0)2 ≤ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 . (3)
When the above holds we have that f(•; θ0) is Lipschitz with constant
L := √ m ‖σ′‖∞ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 .
On the other hand note that
|σ(〈w`, x〉2 + b`)| ≤ |σ(0)|+ ‖σ′‖∞ [|〈w`, x〉2|+ |b`|]. Thus
‖σ(〈w`, x〉2 + b`)‖ψ2 ≤ |σ(0)| ‖1‖ψ2 + ‖σ ′‖∞ [‖|〈w`, x〉2|‖ψ2 + ‖|b`|‖ψ2 ]
≤ |σ(0)| ‖1‖ψ2 + ‖σ ′‖∞ [M ‖w`‖ψ2 + ‖|b`|‖ψ2 ]
≤ 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞}K ≤ DK.
Therefore by Lemma B.11 we have
‖a`σ(〈w`, x〉2 + b`)‖ψ1 ≤ DK 2.
Thus for each x fixed we have by Bernstein’s inequality Vershynin (2018, Theorem 2.8.1)
P (∣∣∣∣∣ m∑ `=1 a`σ(〈w`, x〉2 + b`) ∣∣∣∣∣ > t√m ) ≤ 2 exp ( −cmin [ t2 [DK2]2 , t √ m DK2 ]) .
Thus for t ≤ √ mDK2 this simplifies to
P (∣∣∣∣∣ m∑ `=1 a`σ(〈w`, x〉2 + b`) ∣∣∣∣∣ > t√m ) ≤ 2 exp ( −c t 2 D2K4 ) .
Let ∆ be a γ net of the ball BM = {x : ‖x‖2 ≤M} with respect to the Euclidean ‖•‖2 norm. Then by a standard volume argument we have that
|∆| ≤ ( CM
γ
)d =:Mγ .
Thus by a union bound we have for t ≤ √ mDK2
P ( max x∈∆ ∣∣∣∣∣ m∑ `=1 a`σ(〈w`, x〉2 + b`) ∣∣∣∣∣ > t√m ) ≤ 2Mγ exp ( −c t 2 D2K4 ) .
Thus by setting t = CDK2 √ log(cMγ/δ) assuming t ≤ √ mDK2 we have with probability at least 1− δ
max x∈∆ ∣∣∣∣∣ m∑ `=1 a`√ m σ(〈w`, x〉2 + b`) ∣∣∣∣∣ ≤ t. (4) On the other hand by Lemma B.15 our prior definition of t is large enough (up to a redefinition of the constants c, C) to ensure that with probability at least 1− δ
|b0| ≤ t. (5)
When (4) and (5) hold simultaneously we have that maxx′∈∆ |f(x′, θ0)| ≤ 2t. By a union bound we have with probability at least 1 − 3δ that (3), (4), (5) hold simultaneously. Well then for any x ∈ BM we may choose x′ ∈ ∆ so that ‖x− x′‖2 ≤ γ. Then
|f(x; θ0)| ≤ |f(x′; θ0)|+ |f(x; θ0)− f(x′; θ0)| ≤ 2t+ Lγ.
Therefore sup x∈BM |f(x; θ0)| ≤ 2t+ Lγ
and this argument runs through for any γ > 0. We will set γ = 1/L. Note that for this choice of γ the hypothesis on m ensures that t ≤ √ mDK2. Thus the preceding argument goes through in this case. Thus by replacing δ with δ/3 in the previous argument we get the desired conclusion up to a redefinition of c, C.
We quickly introduce the following lemma. Lemma B.22.
‖r̂(0)‖Rn ≤ ‖f(•; θ0)‖∞ + ‖y‖Rn .
Proof. Let ŷ ∈ Rn be the vector whose ith entry is equal to f(xi; θ0). Well then note that ‖ŷ‖Rn ≤ ‖f(•; θ0)‖∞. Therefore
‖r̂(0)‖Rn = ‖ŷ − y‖Rn ≤ ‖ŷ‖Rn + ‖y‖Rn ≤ ‖f(•; θ0)‖∞ + ‖y‖Rn .
Finally we prove one last lemma that will be useful later.
Lemma B.23. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let Γ > 1, D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1},
L(m,σ, d,K, δ) := √ m ‖σ′‖∞ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 ,
ρ := CDK2 √ d log(CML) + log(c/δ) = Õ( √ d).
Suppose
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2ρ2T 2 [log(Γ)]2 , ( ρ DK2 )2} .
Then with probability at least 1− δ
max t≤T ξ(t) ≤ Γξ(0) max t≤T ξ̃(t) ≤ Γξ̃(0),
where ξ(t) and ξ̃(t) are defined as in Lemmas B.2 and B.3. If one instead does the doubling trick the second hypothesis on m can be removed and the conclusion holds with probability 1. Proof. First assume we are not doing the doubling trick. Well from the condition m ≥ (
ρ DK2
)2 we
have by Lemma B.21 that with probability at least 1− δ
sup x∈BM
|f(x; θ0)| ≤ CDK2 √ d log(CML) + log(c/δ) =: ρ.
Also by Lemma B.22 and the above bound we have
‖r̂(0)‖Rn ≤ ‖y‖Rn + ρ.
Well in this case D ‖r̂(0)‖Rn t√
m ≤ D[‖y‖Rn + ρ]t√ m ≤ 2Dmax{‖y‖Rn , ρ}t√ m ≤ log(Γ),
where we have used the hypothesis on m in the last inequality. Therefore by Lemmas B.2, B.3 we have in this case that
max t≤T ξ(t) ≤ Γξ(0) max t≤T ξ̃(t) ≤ Γξ̃(0)
Now assume we are performing the doubling trick so that f(•; θ0) ≡ 0. Then ρ in the previous argument can simply be replaced with zero and the same argument runs through, except using Lemma B.21 is no longer necessary (and thus the second hypothesis on m is not needed). Without using Lemma B.21 the whole argument is deterministic so that the conclusion holds with probability 1.
B.6 NTK TIME DEVIATIONS BOUNDS
In this section we bound the deviations of the NTK throughout time. This section runs through the following steps
• Bound sup(x,y)∈BM×BM |∂tKt(x, y)| • Bound sup(x,y)∈BM×BM |Kt(x, y)−K0(x, y)|
In the following lemma we will provide an upper bound on the NTK derivative supx,y∈BM×BM |∂tKt(x, y)|. Lemma B.24. Let
ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1},
ξ̃(t) = max{max `∈[m] ‖w`(t)‖2 , ‖a(t)‖∞ , ‖b(t)‖∞ , 1}
D = 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1} D′ := [ max{‖σ′‖∞ , ‖σ ′′‖∞} 2[M2 + 1] +D ‖σ′‖∞ ] max{1,M}.
Then for any initial conditions W (0), b(0), a(0) we have for all t
sup x,y∈BM×BM
|∂tKt(x, y)| ≤ CDD′√
m ξ(t)2ξ̃(t) ‖r̂(t)‖Rn .
Proof. We need to bound the following time derivatives
∂t∂af(x; θ) = ∂tx (1) = − 1
n n∑ i=1 r̂i [ 1√ m σ′1(x)σ ′ 1(xi) a√ m ] [〈x, xi〉2 + 1]
∂t∂W f(x; θ) = ∂t 1√ m σ′1(x)a⊗ x
= 1√ m [(∂tσ ′ 1(x))a+ σ ′ 1(x)(∂ta)]⊗ x
∂t∂bf(x; θ) = ∂t 1√ m σ′1(x)a = 1√ m ([∂tσ ′ 1(x)]a+ σ ′ 1(x)∂ta) .
Note that ∥∥∥∥ 1√mσ′1(x)σ′1(xi) a√m [〈x, xi〉2 + 1] ∥∥∥∥
2
≤ 1√ m ‖σ′‖2∞ 1√ m ‖a‖2 [M 2 + 1].
Thus by Lemma B.1
‖∂t∂af(x; θ)‖2 ≤ 1√ m ‖σ′‖2∞ 1√ m ‖a‖2 [M 2 + 1] ‖r̂(t)‖Rn
≤ ‖σ′‖2∞ [M2 + 1]]√
m ξ(t) ‖r̂(t)‖Rn .
On the other hand
[∂tσ ′ 1(x)]a = −
1
n n∑ i=1 r̂i 1√ m σ′′1 (x)σ ′ 1(xi)diag(a)a[〈x, xi〉2 + 1].
Well 1√ m ‖σ′′1 (x)σ′1(xi)diag(a)a[〈x, xi〉2 + 1‖ ≤ 1√ m ‖σ′′‖∞ ‖σ ′‖∞ ‖a‖∞ ‖a‖2 [M 2 + 1]
≤ ‖σ′′‖∞ ‖σ ′‖∞ [M 2 + 1]ξ(t)ξ̃(t).
Thus by Lemma B.1 we have that
‖[∂tσ′1(x)]a‖ ≤ ‖σ′′‖∞ ‖σ ′‖∞ [M 2 + 1]ξ(t)ξ̃(t) ‖r̂(t)‖Rn . Finally we have
σ′1(x)∂ta = − 1
n n∑ i=1 r̂iσ ′ 1(x)x (1) i .
Well ∥∥∥σ′1(x)x(1)i ∥∥∥ ≤ ‖σ′‖∞ ∥∥∥x(1)i ∥∥∥ 2 = ‖σ′‖∞ 1√ m ‖σ(Wxi + b)‖2
≤ ‖σ′‖∞ [|σ(0)|+ 1√ m ‖σ′‖∞ (‖W‖opM + ‖b‖2)]
≤ ‖σ′‖∞ [|σ(0)|+M ‖σ ′‖∞ + ‖σ ′‖∞] ξ(t) ≤ ‖σ ′‖∞Dξ(t).
Thus we finally by Lemma B.1 again we get that
‖σ′1(x)∂ta‖ ≤ ‖σ′‖∞Dξ(t) ‖r̂(t)‖Rn .
It follows that
‖∂t∂bf(x; θ)‖
≤ 1√ m
[ ‖σ′′‖∞ ‖σ ′‖∞ [M 2 + 1] + ‖σ′‖∞D ] ξ(t)ξ̃(t) ‖r̂(t)‖Rn
and similarly
‖∂t∂W f(x; θ)‖
≤ M√ m
[ ‖σ′′‖∞ ‖σ ′‖∞ [M 2 + 1] + ‖σ′‖∞D ] ξ(t)ξ̃(t) ‖r̂(t)‖Rn .
Thus in total we can say
‖∂t∂af(x; θ)‖2 , ‖∂t∂bf(x; θ)‖2 , ‖∂t∂wf(x; θ)‖F ≤ D′√ m ξ(t)ξ̃(t) ‖r̂(t)‖Rn .
It thus follows by the chain rule and Lemma B.5 that
sup (x,y)∈BM×BM
|∂tKt(x, y)| ≤ CDD′√
m ξ(t)2ξ̃(t) ‖r̂(t)‖Rn .
Using the previous lemma we can now bound the deviations of the NTK. Theorem B.25. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let Γ > 1 and T > 0 be positive constants,
D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ ′‖∞ , 1}, D′ := [ max{‖σ′‖∞ , ‖σ ′′‖∞} 2[M2 + 1] +D ‖σ′‖∞ ] max{1,M},
and assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
Then with probability at least 1− δ
sup (x,y)∈BM×BM
|Kt(x, y)−K0(x, y)| ≤
tΓ3 CDD′√
m ‖r̂(0)‖Rn
{ 1 + C √ d+K2 √ log(c/δ)√
m
}2 {√ d+ CK2 [√ log(c/δ) + √ logm ]} .
If one instead does the doubling trick then the second condition on m can be removed from the hypothesis and the same conclusion holds.
Proof. First assume we are not doing the doubling trick. By Lemmas B.17, B.18 and a union bound we have with probability at least 1− δ
ξ(0)2ξ̃(0) ≤ { 1 + C √ d+K2 √ log(c/δ)√
m
}2 {√ d+ CK2 [√ log(c/δ) + √ logm ]} . (6)
Note that ρ as defined in Lemma B.23 satisfies ρ2 = O(log(c/δ)+Õ(d)). Thus the hypothesis onm is strong enough to apply Lemma B.23, therefore by applying this lemma we have with probability at least 1− δ
max t≤T ξ(t) ≤ Γξ(0) max t≤T ξ̃(t) ≤ Γξ̃(0). (7)
Thus by replacing δ with δ/2 and taking a union bound we have that with probability at least 1− δ (6) and (7) hold simultaneously. Then using Lemma B.24 and the fact that ‖r̂(t)‖Rn ≤ ‖r̂(0)‖Rn we have for t ≤ T
sup (x,y)∈BM×BM
|∂tKt(x, y)| ≤ Γ3 CDD′√
m ξ(0)2ξ̃(0) ‖r̂(0)‖Rn .
Therefore by the fundamental theorem of calculus for t ≤ T
sup (x,y)∈BM×BM
|Kt(x, y)−K0(x, y)| ≤ tΓ3 CDD′√
m ξ(0)2ξ̃(0) ‖r̂(0)‖Rn
≤ tΓ3CDD ′
√ m ‖r̂(0)‖Rn
{ 1 + C √ d+K2 √ log(c/δ)√
m
}2 {√ d+ CK2 [√ log(c/δ) + √ logm ]} .
Now consider if one instead does the doubling trick where one does the following swaps W (0) →[ W (0) W (0) ] , b(0) → [ b(0) b(0) ] , a(0) → [ a(0) −a(0) ] and m → 2m where W (0), b(0), and a(0) are initial-
ized as before. Then ξ(0) and ξ̃(0) do not change. We can then run through the same exact proof as before except when we apply Lemma B.23 the second hypothesis on m is no longer needed.
Theorem B.26. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Let Γ > 1 and T > 0 be positive constants and let D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}. Assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
Then with probability at least 1− δ we have for t ≤ T
sup (x,y)∈BM×BM
|Kt(x, y)−K∞(x, y)| = Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
If one instead does the doubling trick then one can remove the assumption m ≥ 4D2O(log(c/δ)+Õ(d))T 2
[log(Γ)]2 and have the same conclusion hold.
Proof. The condition m ≥ O(log(c/δ) + Õ(d)) is sufficient to satisfy the hypothesis of Theorem B.19. The condition on m also immediately satisfies the hypothesis of Theorem B.25. The desired result then follows from a union bound.
Theorem B.27. Under the same assumptions as Theorem B.26 we have that with probability at least 1− δ for all t ≤ T
‖H∞ −Ht‖op ≤ nÕ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ])
sup s≤T ‖G∞ −Gt‖op ≤ Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
Proof. Recall that for a matrix A ∈ Rm×n ‖A‖op ≤ √ mnmaxi,j |Ai,j |. Thus by Theorem B.26 with probability at least 1− δ
‖H∞ −Ht‖op ≤ nmaxi,j |H ∞ i,j − (Ht)i,j | ≤ n sup (x,y)∈BM×BM |Kt(x, y)−K∞(x, y)|
= nÕ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
The second bound follows from Gs = 1nHs and G ∞ = 1nH ∞.

heading: B.7 NTK DEVIATIONS FOR RELU APPROXIMATIONS
text: The NTK deviation bounds given in the previous subsections assumed ‖σ′′‖∞ < ∞. For ReLU this assumption is not satisfied. It is natural to ask to what extent we might expect the results to hold when the activation function is σ(x) = ReLU(x) = max{0, x}. The closest we can get to ReLU without modifying the proofs is to use the Softmax approximation to ReLU, namely σ(x) = 1α ln(1 + exp(αx)), and consider what happens as α → ∞. For this choice of σ we have that ‖σ′′‖∞ = O(α). In Subsection B.6 where you will pay the biggest penalty is in Theorem B.25 via the constant D′ = O(‖σ′′‖2∞) = O(α2). Since the final bound depends on the ratio D′√ m
you will have that m will grow like O(α4). This is no moderate penalty, although we might expect the results to hold for wide ReLU networks if a finite α provides a reasonable approximation. In particular Softmax ln(1 + exp(x)) leads to a fixed constant for D′.

heading: C UNDERPARAMETERIZED REGIME
text: In this section we build the tools to study the implicit bias in the underparameterized case. Our ultimate goal is prove Theorem 3.5.
Outline of this section
• Review operator theory
• Prove damped deviations equation
• Bound ‖(TK∞ − T sn)rt‖2 – Bound ‖(Tn − T sn)rt‖2 using NTK deviation results (comparatively easy) – Bound ‖(TK∞ − Tn)rt‖2
* Derive covering number for a class of functions C * Use covering number to bound supg∈C ‖(TK∞ − Tn)g‖ * Show that rt is in class C
• Prove Theorem 3.5

heading: C.1 RKHS AND MERCER’S THEOREM
text: We recall some facts about Reproducing Kernel Hilbert Spaces (RKHS) and Mercer’s Theorem. For additional background we suggest Berlinet & Thomas-Agnan (2004). Let X ⊂ Rd be a compact space equipped with a strictly positive (regular Borel) probability measure ρ. LetK : X×X → R be a continuous, symmetric, positive definite function. We define the integral operator TK : L2ρ(X)→ L2ρ(X)
TKf(x) := ∫ X K(x, s)f(s)dρ(s).
In this setting TK is a compact, positive, self-adjoint operator. By the spectral theorem there is a countable nonincreasing sequence of nonnegative values {σi}∞i=1 and an orthonormal set {φi}∞i=1 in L2 such that TKφi = σiφi. We will assume that TK is strictly positive, i.e. 〈f, TKf〉2 > 0 for f 6= 0, so that we have further that {φi}∞i=1 is an orthonormal basis of L2 and σi > 0 for all i. Moreover since K is continuous we may select the φi so that they are continuous functions, i.e. φi ∈ C(X) for each i. Then by Mercer’s theorem we can decompose
K(x, y) = ∞∑ i=1 σiφi(x)φi(y),
where the convergence is uniform. Furthermore the RKHS H associated with K is given by the set of functions
H = { f ∈ L2 :
∞∑ i=1 |〈f, φi〉2|2 σi <∞
} ,
where the inner product onH is given by 〈f, g〉H = ∞∑ i=1 〈f, φi〉2〈g, φi〉2 σi . Note that in this setting {√σiφi}∞i=1 is an orthonormal basis of H. Define Kx := K(•, x). Recall the RKHS has the defining properties
Kx ∈ H ∀x ∈ X h(x) = 〈h,Kx〉H ∀(x, h) ∈ X ×H.
We will let κ := supx∈X K(x, x) <∞. From this we will have the useful inequality: for h ∈ H |h(x)| = |〈h,Kx〉H| ≤ ‖h‖H ‖Kx‖H = ‖h‖H √ 〈Kx,Kx〉H = ‖h‖H √ K(x, x)
≤ κ1/2 ‖h‖H . Furthermore the elements ofH are bounded continuous functions andH is seperable.

heading: C.2 HILBERT-SCHMIDT AND TRACE CLASS OPERATORS
text: We will recall some definitions from (Rosasco et al., 2010). A bounded operator on a separable Hilbert space with associated norm ‖•‖ is called Hilbert-Schmidt if
∞∑ i=1 ‖Aei‖2 <∞
for some (any) orthonormal basis {ei}i. For such an operator we define its Hilbert-Schmidt norm ‖A‖HS to be the square root of the above sum. The Hilbert-Schmidt norm is the analog of the Frobenius norm for matrices. It is useful to note that every Hilbert-Schmidt operator is compact. The space of Hilbert-Schmidt operators is a Hilbert space with respect to the inner product
〈A,B〉 = ∑ j 〈Aej , Bej〉.
A stronger notion is that of a trace class operator. We say a bounded operator on a separable Hilbert space is trace class if
∞∑ i=1 〈 √ A∗Aei, ei〉 <∞
for some (any) orthonormal bases {ei}i. For such an operator we may define
Tr(A) := ∞∑ i=1 〈Aei, ei〉.
By Lidskii’s theorem the above sum is also equal to the sum of the eigenvalues of A repeated by multiplicity. The space of trace class operators is a Banach space with the norm ‖A‖TC = Tr( √ A∗A). The following inequalities will be useful
‖A‖ ≤ ‖A‖HS ≤ ‖A‖TC . Furthermore if A is Hilbert-Schmidt and B is bounded we have
‖BA‖HS , ‖AB‖HS ≤ ‖A‖HS ‖B‖ . Note that in our setting we have
κ ≥ ∫ X K(x, x)dρ(x) = ∫ X ∞∑ i=1 σi|φi(x)|2dρ(x) = ∞∑ i=1 σi ∫ X |φi(x)|2dρ(x)
= ∞∑ i=1 σi = Tr(TK),
where the interchange of integration and summation is justified by the monotone convergence theorem. Thus TK is a trace class operator and we have the inequality
κ ≥ ∞∑ i=1 σi
which will prove useful later.

heading: C.3 DAMPED DEVIATIONS
text: Let x 7→ gs(x) ∈ L2 for each s ∈ [0, t] such that s 7→ 〈φi, gs〉2 is measureable for each i and∫ t 0 ‖gs‖22 <∞. Then we define the integral ∫ t
0
gsds coordinatewise, meaning that ∫ t
0 gsds is the L2 function h such that 〈h, φi〉2 = ∫ t
0
〈gs, φi〉2ds.
Using this definition, we can now prove the “Damped Deviations” lemma. Lemma 2.3. Let K(x, x′) be an arbitrary continuous, symmetric, positive-definite kernel. Let [TKh](•) = ∫ X K(•, s)h(s)dρ(s) be the integral operator associated with K and let [T snh](•) = 1 n ∑n i=1Ks(•, xi)h(xi) denote the operator associated with the time-dependent NTK Ks. Then
rt = exp(−TKt)r0 + ∫ t
0
exp(−TK(t− s))(TK − T sn)rsds,
where the equality is in the L2 sense.
Proof. We have that
∂srs(x) = − 1
n n∑ i=1 Ks(x, xi)rs(xi) = −[T snrs](x),
where the equality is pointwise over x. ∂srs(x) is a continuous function of x since Ks is continuous and is thus in L2. Therefore we can consider
〈∂srs, φi〉2 = 〈−T snrs, φi〉2.
By the continuity of s 7→ θs we have the parameters are locally bounded in time and thus by Lemma B.5 we have that ‖Ks‖∞ is also locally bounded therefore for any δ > 0, s0: sup|s−s0|≤δ ‖Ks‖∞ < ∞. Note then that
|∂srs(x)| ≤ 1
n n∑ i=1 |Ks(x, xi)||rs(xi)| ≤ ‖Ks‖∞ ‖r̂s‖Rn ≤ ‖Ks‖∞ ‖r̂0‖Rn .
It follows that ‖∂srs‖∞ is bounded locally uniformly in s. Therefore the following differentiation under the integral sign is justified
d
ds 〈rs, φi〉2 = 〈∂srs, φi〉2.
Thus combined with our previous equality we get d
ds 〈rs, φi〉2 = 〈−T snrs, φi〉2 = 〈−TKrs, φi〉2 + 〈(TK − T sn)rs, φi〉2
= 〈rs,−TKφi〉2 + 〈(TK − T sn)rs, φi〉2 = −σi〈rs, φi〉2 + 〈(TK − T sn)rs, φi〉2, where we have used that TK is self-adjoint. Therefore
d
ds 〈rs, φi〉2 + σi〈rs, φi〉2 = 〈(TK − T sn)rs, φi〉2.
Multiplying by the integrating factor exp(σis) we get d
ds [exp(σis)〈rs, φi〉2] = exp(σis)〈(TK − T sn)rs, φi〉2.
Therefore applying the fundamental theorem of calculus after rearrangement we get 〈rt, φi〉2 = exp(−σit)〈r0, φi〉2 + ∫ t
0
exp(−σi(t− s))〈(TK − T sn)rs, φi〉2ds,
which is just the coordinatewise version of the desired result. rt = exp(−TKt)r0 + ∫ t
0
exp(−TK(t− s))(TK − T sn)rsds.

heading: C.4 COVERING NUMBER OF CLASS
text: We will now estimate the covering number of the class of shallow networks with bounds on their parameter norms. This lemma is slightly more general than what we will use but we will particularize it latter as it’s general formulation presents no additional difficulty.
Lemma C.1. Let
C = { a T
√ m σ(Wx+ b) + b0 : ‖a− a′‖2 ≤ ρ1, ‖W −W ′‖F ≤ ρ2,
‖b− b′‖2 ≤ ρ3, |b0 − b ′ 0| ≤ ρ4
1√ m ‖a‖2 ≤ ρ ′ 1, 1√ m ‖W‖op ≤ ρ ′ 2, 1√ m ‖b‖2 ≤ ρ ′ 3 }
and γ′ := |σ(0)|+ ‖σ′‖∞ [ρ ′ 2M + ρ ′ 3] .
Then the (proper) covering number of C in the uniform norm satisfies N (C, , ‖‖∞) ≤ ( C ′ )p where p = md+ 2m+ 1 is the total number of parameters and C ′ equals
C ′ = C max {ρ1γ′, ρ2M ‖σ′‖∞ ρ ′ 1, ρ3 ‖σ′‖∞ ρ ′ 1, ρ4} ,
where C > 0 is an absolute constant.
Proof. We will bound the pertubation of the function when changing the weights, specifically we will bound
sup x∈BM ∣∣∣∣ aT√mσ(Wx+ b)− ãT√mσ(W̃x+ b̃) ∣∣∣∣ .
Let x(1) = 1√ m σ(Wx+ b) and x̃(1) = 1√ m σ(W̃x+ b̃). Then note that we have∥∥∥x(1) − x̃(1)∥∥∥
2 ≤ 1√ m ‖σ′‖∞ ∥∥∥(W − W̃ )x+ b− b̃∥∥∥ 2
≤ 1√ m ‖σ′‖∞ [∥∥∥W − W̃∥∥∥ op ‖x‖2 + ∥∥∥b− b̃∥∥∥ 2 ] ≤ 1√
m ‖σ′‖∞ [∥∥∥W − W̃∥∥∥ F M + ∥∥∥b− b̃∥∥∥ 2 ] =: γ.
Well then
|aTx(1) − ãT x̃(1)| ≤ |aT (x(1) − x̃(1))|+ |(a− ã)T x̃(1)| ≤ ‖a‖2 γ + ‖a− ã‖2 ∥∥∥x̃(1)∥∥∥
2 .
Finally ∥∥∥x̃(1)∥∥∥ 2 = ∥∥∥∥ 1√mσ(W̃x+ b̃) ∥∥∥∥
2
≤ |σ(0)|+ 1√ m ‖σ′‖∞ ∥∥∥W̃x+ b̃∥∥∥ 2
≤ |σ(0)|+ 1√ m ‖σ′‖∞ [∥∥∥W̃∥∥∥ op ‖x‖2 + ∥∥∥b̃∥∥∥ 2 ] ≤ |σ(0)|+ 1√
m ‖σ′‖∞ [∥∥∥W̃∥∥∥ op M + ∥∥∥b̃∥∥∥ 2 ] ≤ |σ(0)|+ ‖σ′‖∞ [ρ ′ 2M + ρ ′ 3] =: γ ′.
Therefore |aTx(1) − ãT x̃(1)| ≤ ‖a‖2 γ + ‖a− ã‖2 γ ′.
Thus if we have
‖a− ã‖2 ≤ 4γ′ =: 1, ∥∥∥W − W̃∥∥∥ F ≤ 8M ‖σ′‖∞ ρ′1 =: 2, ∥∥∥b− b̃∥∥∥ 2 ≤ 8 ‖σ′‖∞ ρ′1 =: 3,
then
‖a‖2 γ ≤ ‖a‖2
4ρ′1 √ m ≤ 4 .
Therefore |aTx(1) − ãT x̃(1)| ≤ /2
and this bound holds for any x ∈ BM . If add biases b0 and b̃0 such that |b0 − b̃0| ≤ /2 we simply get by the triangle inequality
|aTx(1) + b0 − (ãT x̃(1) + b̃0)| ≤ .
Thus to get a cover we can simply cover the sets
{a : ‖a− a′‖2 ≤ ρ1} {W : ‖W −W ′‖F ≤ ρ2}
{b : ‖b− b′‖2 ≤ ρ3} {b0 : |b0 − b ′ 0| ≤ ρ4}
in the Euclidean norm and multiply the covering numbers. Recall that the covering number for a Euclidean ball of radius R in Rs, say N , using the Euclidean norm satisfies(
cR )s ≤ N ≤ ( CR )s for two absolute constants c, C > 0. Therefore we get that
N (C, , ‖‖∞) ≤ ( Cρ1 1 )m( Cρ2 2 )md( Cρ3 3 )m( 2Cρ4 ) .
The desired result follows from
max { ρ1 1 , ρ2 2 , ρ3 3 , 2ρ4 } ≤ C max {ρ1γ′, ρ2M ‖σ′‖∞ ρ ′ 1, ρ3 ‖σ′‖∞ ρ ′ 1, ρ4} .
We can now prove the following corollary which is the version of the previous lemma that we will actually use for our neural network. Corollary C.2. Let
C = { a T
√ m σ(Wx+ b) + b0 : 1√ m ‖a‖2 , 1√ m ‖W‖op , 1√ m ‖b‖2 ≤ A, |b0| ≤ B }
and γ′ := |σ(0)|+ ‖σ′‖∞ [AM +A] and assume m ≥ d. Then the (proper) covering number of C in the uniform norm satisfies
N (C, , ‖‖∞) ≤ ( Ψ(m, d) )p ,
where
Ψ(m, d) = C max{ √ mAγ′, √ mdA2 ‖σ′‖∞M, √ mA2 ‖σ′‖∞ , B}
= √ mdO ( max { A2,
B√ md
}) .
Proof. The idea is to apply Lemma C.1 with a′ = 0, W ′ = 0, b′ = 0, and b′0 = 0. Note that ‖W‖F ≤ √ d ‖W‖op ≤ √ mdA. The result then follows by applying lemma with ρ1 = √ mA, ρ2 = √ mdA, ρ3 = √ mA and ρ4 = B and ρ′1 = ρ ′ 2 = ρ ′ 3 = A.

heading: C.5 UNIFORM CONVERGENCE OVER THE CLASS
text: We now show that ‖(Tn − TK∞)g‖2 is uniformly small for all g in a suitable class of functions C′. Ultimately we will show that rt ∈ C′ and thus this result is towards proving that ‖(Tn − TK∞)rt‖2 is small. Lemma C.3. Let K(x, x′) by a continuous, symmetric, positive-definite kernel and let κ = maxx∈X K(x, x) < ∞. Let TKh(•) = ∫ X K(•, s)h(s)dρ(s) and Tnh(•) = 1 n ∑n i=1K(•, xi)h(xi) be the associated operators. Let σ1 denote the largest eigenvalue of TK . Let C and Ψ(m, d) be defined as in Corollary C.2. We let C′ = {g− f∗ : g ∈ C}∩ {g : ‖g‖∞ ≤ S} be the set where C is translated by the target function f∗ then intersected with the L∞ ball of radius S > 0. Then with probability at least 1− δ over the sampling of x1, . . . , xn
sup g∈C′ ‖(Tn − TK)g‖2 ≤
2S √ σ1κ √ 2 log(c/δ) + 2p log(‖K‖∞Ψ(m, d) √ n)√
n + 2√ n
=
2 [ 1 + S √ σ1κ √ 2 log(c/δ) + Õ(p) ] √ n .
Proof. Let g ∈ C′. We introduce the random variables Yi := Kxig(xi) − Ex∼ρ[Kxg(x)] taking values in the Hilbert spaceH for i ∈ [n] whereH is the RKHS associated with K. Note that for any x
‖Kxg(x)‖H = |g(x)| √ 〈Kx,Kx〉H ≤ S √ K(x, x) ≤ Sκ1/2.
Thus ‖Yi‖H ≤ 2Sκ1/2 a.s. Thus by Hoeffding’s inequality for random variables taking values in a separable Hilbert space (see Rosasco et al. (2010, Section 2.4)) we have
P (∥∥∥∥∥ 1n n∑ i=1 Yi ∥∥∥∥∥ H > t ) ≤ 2 exp ( −nt2/2[2Sκ1/2]2 ) .
Note that by basic properties of the covering number we have thatN (C′, , ‖‖∞) ≤ N (C, /2, ‖‖∞), thus by Corollary C.2 the covering number of C′ satisfies (up to a redefinition of C)
N (C′, , ‖‖∞) ≤ ( Ψ(m, d) )p .
Let ∆ be an net of C′ in the uniform norm. Note that 1n ∑n i=1 Yi = (Tn − TK)g. Thus by taking a union bound we have
P (
max g∈∆ ‖(Tn − TK)g‖H ≥ t
) ≤ ( Ψ(m, d) )p 2 exp ( −nt2/2[2Sκ1/2]2 ) .
Note that for any probability measure ν and h ∈ L∞∣∣∣∣∫ X K(x, s)h(s)dν(s) ∣∣∣∣ ≤ ∫ X |K(x, s)||h(s)|dν(s) ≤ ‖K‖∞ ‖h‖∞ .
It follows that for any h ∈ L∞
‖(TK − Tn)h‖∞ ≤ 2 ‖K‖∞ ‖h‖∞ . Note for any g ∈ C′ we can pick ĝ in ∆ such that ‖g − ĝ‖∞ ≤ . Then
‖(Tn − TK)g‖2 ≤ ‖(Tn − TK)ĝ‖2 + ‖(Tn − TK)(g − ĝ)‖2 ≤ √ σ1 ‖(Tn − TK)ĝ‖H + ‖(Tn − TK)(g − ĝ)‖∞
≤ √ σ1t+ 2 ‖K‖∞ ‖g − ĝ‖∞ ≤ √ σ1t+ 2 ‖K‖∞ ,
where we have used the fact that ‖•‖2 ≤ √ σ1 ‖•‖H and ‖•‖2 ≤ ‖•‖∞ in the second inequality. Thus by setting
t = 2Sκ1/2 √ 2 log(c/δ) + 2p log(Ψ(m, d)/ )√
n
we have with probability at least 1− δ
sup g∈C′ ‖(Tn − TK)g‖2 ≤
√ σ1
2Sκ1/2 √
2 log(c/δ) + 2p log(Ψ(m, d)/ )√ n + 2 ‖K‖∞ .
This argument runs through for any > 0. Thus by setting = 1‖K‖∞ √ n we get the desired result.

heading: C.6 NEURAL NETWORK IS IN THE CLASS
text: In this section we demonstrate that the neural network in such a class as C as defined in Lemma C.1. Once we have this we can use Lemma C.3 to show that ‖(TK∞ − Tn)rt‖2 is uniformly small. The first step is to bound the parameter norms, hence the following lemma. Lemma C.4. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}, and
ξ(t) = max{ 1√ m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2 , 1}.
Furthermore assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
Then with probability at least 1− δ
max t∈[0,T ]
ξ(t) ≤ Γ [ 1 + C √ d+K2 √ log(c/δ)√
m
] .
If one instead does the doubling trick then the second condition on m can be removed from the hypothesis and the same conclusion holds.
Proof. First assume we are not doing the doubling trick. Note that the hypothesis on m is strong enough to satisfy the hypothesis of Lemma B.23, therefore we have with probability at least 1− δ
max t≤T
ξ(t) ≤ Γξ(0).
Well then separately by Lemma B.17 with probability at least 1− δ
ξ(0) ≤ 1 + C √ d+K2 √ log(c/δ)√
m .
Thus by replacing δ with δ/2 in the previous statements and taking a union bound we have with probability at least 1− δ
max t∈[0,T ]
ξ(t) ≤ Γ [ 1 + C √ d+K2 √ log(c/δ)√
m ] which is the desired result. Now suppose instead one does the doubling trick. We recall that the doubling trick does not change ξ(0). Thus we can run through the exact same argument as before except when we apply Lemma B.23 we can remove the second condition on m from the hypothesis.
The following lemma bounds the bias term. Lemma C.5. For any initial conditions we have
|b0(t)| ≤ |b0(0)|+ t ‖r̂(0)‖Rn .
Proof. Note that
|∂tb0(t)| = ∣∣∣∣∣ 1n n∑ i=1 r̂(t)i ∣∣∣∣∣ ≤ ‖r̂(t)‖Rn ≤ ‖r̂(0)‖Rn Thus by the fundamental theorem of calculus
|b0(t)| ≤ |b0(0)|+ t ‖r̂(0)‖Rn .
The following lemma demonstrates that the residual rt = ft − f∗ is bounded. Lemma C.6. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}, and assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
Then with probability at least 1− δ for t ≤ T
‖ft − f∗‖∞ ≤ ‖f0 − f ∗‖∞ + t ‖r̂(0)‖Rn CD 2Γ2
[ 1 + C √ d+K2 √ log(c/δ)√
m ]2 If one instead does the doubling trick then the second condition on m can be removed from the hypothesis and the same conclusion holds.
Proof. Recall that
∂t(ft(x)− f∗(x)) = − 1
n n∑ i=1 Kt(x, xi)(ft(xi)− f∗(xi)) = − 1 n n∑ i=1 Kt(x, xi)r̂(t)i.
Thus
|∂t(ft(x)− f∗(x))| ≤ 1
n n∑ i=1 |Kt(x, xi)||r̂(t)i| ≤ ‖Kt‖∞ ‖r̂(t)‖Rn ≤ ‖Kt‖∞ ‖r̂(0)‖Rn .
Well by Lemma B.5 we have that ‖Kt‖∞ ≤ CD2ξ2(t) where
ξ(t) = max{ 1√ m ‖W‖op , 1√ m ‖b‖2 , 1√ m ‖a‖2 , 1}.
Well by Lemma C.4 we have that with probability at least 1− δ
max t∈[0,T ]
ξ(t) ≤ Γ [ 1 + C √ d+K2 √ log(c/δ)√
m
] .
Thus by the fundamental theorem of calculus for t ≤ T
|ft(x)− f∗(x)| ≤ |f0(x)− f∗(x)|+ t ‖r̂(0)‖Rn CD 2Γ2
[ 1 + C √ d+K2 √ log(c/δ)√
m ]2 Thus by taking the supremum over x we get
‖ft − f∗‖∞ ≤ ‖f0 − f ∗‖∞ + t ‖r̂(0)‖Rn CD 2Γ2
[ 1 + C √ d+K2 √ log(c/δ)√
m ]2 which is the desired conclusion.
We can now finally prove that ‖(TK∞ − Tn)rt‖2 is uniformly small.
Lemma C.7. Let K(x, x′) by a continuous, symmetric, positive-definite kernel and let κ = maxxK(x, x) < ∞. Let TKh(•) = ∫ X K(•, s)h(s)dρ(s) and Tnh(•) = 1n ∑n i=1K(•, xi)h(xi) be the associated operators. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 , ‖b0‖ψ2 ≤ K
′ for each ` ∈ [m] where K ′ ≥ 1. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}, and assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
If we are doing the doubling trick set S′ = 0 and otherwise set S′ = CD(K ′)2 √ d log(CMÕ( √ m)) + log(c/δ) = Õ( √ d).
Then with probability at least 1− δ
sup t≤T ‖(Tn − TK)rt‖2 = Õ
( (‖f∗‖∞ + S′)(1 + TΓ2) √ σ1κp√
n ) and
‖r0‖∞ ≤ ‖f ∗‖∞ + S ′.
If we are performing the doubling trick the second condition on m can be removed and the same conclusion holds.
Proof. By Lemma C.4 we have with probability at least 1− δ
max t∈[0,T ]
ξ(t) ≤ Γ [ 1 + C √ d+ (K ′)2 √ log(c/δ)√
m
] =: A. (8)
Also by Lemma C.5 |b0(t)| ≤ |b0(0)|+ t ‖r̂(0)‖Rn .
If we are doing the doubling trick then b0(0) = 0. Otherwise by Lemma B.15 we have with probability at least 1− δ |b0(0)| ≤ CK ′ √ log(c/δ).
Furthermore by Lemma B.22 we have
‖r̂(0)‖Rn ≤ ‖y‖Rn + ‖f(•; θ0)‖∞ .
Let L be defined as in Lemma B.21, i.e.
L(m,σ, d,K ′, δ) := √ m ‖σ′‖∞ { 1 + C √ d+ (K ′)2 √ log(c/δ)√
m
}2 = Õ( √ m).
If we are not performing the doubling trick set S′ = CD(K ′)2 √ d log(CML) + log(c/δ).
Otherwise if we are performing the doubling trick set S′ = 0. In either case by Lemma B.21 we have with probability at least 1− δ
‖f(•; θ0)‖∞ ≤ S ′. (9)
In particular by Lemma B.22 we have
‖r̂(0)‖Rn ≤ ‖y‖Rn + ‖f(•; θ0)‖∞ ≤ ‖y‖Rn + S ′.
Thus we can say |b0(t)| ≤ |b0(0)|+ t ‖r̂(0)‖Rn ≤ CK ′ √ log(c/δ) + T (‖y‖Rn + S ′) =: B
and this holds whether or not we are performing the doubling trick. Thus up until time T the neural network is in class C as defined in Corollary C.2 with parameters A and B as defined above.
Moreover by Lemma C.6 separate from the randomness before we have that with probability at least 1− δ
‖rt‖∞ ≤ ‖r0‖∞ + t ‖r̂(0)‖Rn CD 2Γ2
[ 1 + C √ d+ (K ′)2 √ log(c/δ)√
m ]2 Well note that when (9) holds we have
‖r̂(0)‖Rn ≤ ‖r0‖∞ ≤ ‖f ∗‖∞ + ‖f(•; θ0)‖∞ ≤ ‖f ∗‖∞ + S ′.
Thus
‖rt‖∞ ≤ (‖f ∗‖∞ + S ′) 1 + TCD2Γ2 [ 1 + C √ d+ (K ′)2 √ log(c/δ)√ m ]2 =: S Thus by taking a union bound and redefining δ we have by an application of Lemma C.3 with S as defined in the hypothesis of the current theorem that with probability at least 1− δ
sup t≤T ‖(Tn − TK)rt‖2 ≤
2 [ 1 + S √ σ1κ √ 2 log(c/δ) + Õ(p) ] √ n
= Õ
( (‖f∗‖∞ + S′)(1 + TΓ2) √ σ1κp√
n ) where we have used that S = Õ([‖f∗‖∞ + S′][1 + TΓ2]).

heading: C.7 PROOF OF THEOREM 3.5
text: We are almost ready to prove Theorem 3.5. However first we must introduce a couple lemmas. The following lemma uses the damped deviations equation to bound the difference between rt and exp(−TKt)r0. Lemma C.8. Let K(x, x′) by a continuous, symmetric, positive-definite kernel with associated operator TKh(•) = ∫ X K(•, s)h(s)dρ(s). Let T snh(•) = 1n ∑n i=1Ks(•, xi)h(xi) denote the operator associated with the time-dependent NTK. Then
‖Pk(rt − exp(−TKt)r0)‖2 ≤ 1− exp(−σkt)
σk sup s≤t ‖(TK − T sn)rs‖2 .
and
‖rt − exp(−TKt)r0‖2 ≤ t · sup s≤t ‖(TK − T sn)rs‖2 .
Proof. From Lemma 2.3 we have
rt = exp(−TKt)r0 + ∫ t
0
exp(−TK(t− s))(TK − T sn)rsds.
Thus for any k ∈ N
Pk(rt − exp(−TKt)r0) = Pk ∫ t
0
exp(−TK(t− s))(TK − T sn)rsds
= ∫ t 0 Pk exp(−TK(t− s))(TK − T sn)rsds.
Therefore ‖Pk(rt − exp(−TKt)r0)‖2 = ∥∥∥∥∫ t
0
Pk exp(−TK(t− s))(TK − T sn)rsds ∥∥∥∥
2 ≤ ∫ t
0
‖Pk exp(−TK(t− s))(TK − T sn)rs‖2 ds
≤ ∫ t
0
‖Pk exp(−TK(t− s))‖ ‖(TK − T sn)rs‖2 ds
≤ ∫ t
0
exp(−σk(t− s)) ‖(TK − T sn)rs‖2 ds
≤ 1− exp(−σkt) σk sup s≤t ‖(TK − T sn)rs‖2 .
Similarly
‖rt − exp(−TKt)r0‖2 = ∥∥∥∥∫ t
0
exp(−TK(t− s))(TK − T sn)rsds ∥∥∥∥
2 ≤ ∫ t
0
‖exp(−TK(t− s))(TK − T sn)rs‖2 ds
≤ ∫ t
0
‖exp(−TK(t− s))‖ ‖(TK − T sn)rs‖2 ds
≤ ∫ t
0
‖(TK − T sn)rs‖2 ds ≤ t · sup s≤t ‖(TK − T sn)rs‖2 .
In light of the previous lemma we would like to have a bound for ‖(TK − T sn)rs‖2. This is accomplished by the following lemma. Lemma C.9. Let K(x, x′) by a continuous, symmetric, positive-definite kernel. Let TKh(•) =∫ X K(•, s)h(s)dρ(s) and Tnh(•) = 1n ∑n i=1K(•, xi)h(xi) be the associated operators. Let
T snh(•) = 1n ∑n i=1Ks(•, xi)h(xi) denote the operator associated with the time-dependent NTK. Then sup s≤T ‖(TK − T sn)rs‖2 ≤ sup s≤T ‖(TK − Tn)rs‖2 + sup s≤T ‖K −Ks‖∞ ‖r̂(0)‖Rn .
Proof. We have that
‖(TK − T sn)rs‖2 ≤ ‖(TK − Tn)rs‖2 + ‖(Tn − T s n)rs‖2 .
Now observe that
|(Tn − T sn)rs(x)| = ∣∣∣∣∣ 1n n∑ i=1 [K(x, xi)−Ks(x, xi)]rs(xi) ∣∣∣∣∣ ≤ 1 n n∑ i=1 |K(x, xi)−Ks(x, xi)||rs(xi)|
≤ ‖K −Ks‖∞ ‖r̂(s)‖Rn ≤ ‖K −Ks‖∞ ‖r̂(0)‖Rn .
Therefore ‖(Tn − T sn)rs‖2 ≤ ‖(Tn − T s n)rs‖∞ ≤ ‖K −Ks‖∞ ‖r̂(0)‖Rn .
Thus sup s≤T ‖(TK − T sn)rs‖2 ≤ sup s≤T ‖(TK − Tn)rs‖2 + sup s≤T ‖K −Ks‖∞ ‖r̂(0)‖Rn .
We are almost ready to finally prove Theorem 3.5. We must prove one final lemma that combines Lemma C.7 with the NTK deviation bounds in Theorem B.26 to show that ‖(TK∞ − T sn)rs‖2 is uniformly small.
Lemma C.10. Assume that Wi,j ∼ W , b` ∼ B, a` ∼ A are all i.i.d zero-mean, subgaussian random variables with unit variance. Furthermore assume ‖1‖ψ2 , ‖w`‖ψ2 , ‖a`‖ψ2 , ‖b`‖ψ2 ≤ K for each ` ∈ [m] where K ≥ 1. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}, and assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d))
} .
If we are doing the doubling trick set S′ = 0 and otherwise set S′ = CDK2 √ d log(CMÕ( √ m)) + log(c/δ) = Õ( √ d), S = S′ + ‖f∗‖∞ .
Then with probability at least 1− δ
sup s≤t ‖(TK∞ − T sn)rs‖2 = Õ
( S
√ d√ m [ 1 + tΓ3S ] + S(1 + TΓ2) √ σ1κp√ n
) .
If we are performing the doubling trick the condition m ≥ 4D 2O(log(c/δ)+Õ(d))T 2
[log(Γ)]2 can be removed and the same conclusion holds.
Proof. Note by Lemma C.9 we have
sup s≤T ‖(TK∞ − T sn)rs‖2 ≤ sup s≤T ‖(TK∞ − Tn)rs‖2 + sup s≤T ‖K∞ −Ks‖∞ ‖r̂(0)‖Rn .
Well then by Theorem B.26 we have with probability at least 1− δ that
sup t≤T ‖Kt −K∞‖∞ = Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
Separately by Lemma C.7 we have with probability at least 1− δ
sup s≤T ‖(TK∞ − Tn)rs‖2 = Õ
( (‖f∗‖∞ + S′)(1 + TΓ2) √ σ1κp√
n
) = Õ ( S(1 + TΓ2) √ σ1κp√
n ) and ‖r̂(0)‖Rn ≤ ‖r0‖∞ ≤ S. The result follows then from taking a union bound and replacing δ with δ/2.
We now proceed to prove the main theorem of this paper.
Theorem 3.5. Assume that Assumptions 3.3 and 3.4 hold. Let Pk be the orthogonal projection in L2 onto span{φ1, . . . , φk} and let D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}. If we are doing the doubling trick set S′ = 0 and otherwise set S′ = O (√ Õ(d) + log(c/δ) ) , S = ‖f∗‖∞ + S′.
Also let T > 0. Assumem ≥ D2 ‖y‖2Rn T 2, andm ≥ O(log(c/δ)+ Õ(d)) max { T 2, 1 } . Then with probability at least 1− δ we have that for all t ≤ T and k ∈ N
‖Pk(rt − exp(−TK∞t)r0)‖2 ≤ 1− exp(−σkt)
σk Õ
( S [1 + tS]
√ d√ m + S(1 + T ) √ p √ n ) and
‖rt − exp(−TK∞t)r0‖2 ≤ tÕ
( S [1 + tS]
√ d√ m + S(1 + T ) √ p √ n
) .
Proof. By Lemma C.8 we have for any k ∈ N
‖Pk(rt − exp(−TK∞t)r0)‖2 ≤ 1− exp(−σkt)
σk sup s≤t ‖(TK∞ − T sn)rs‖2
and furthermore ‖rt − exp(−TK∞t)r0‖ ≤ t sup
s≤t ‖(TK∞ − T sn)rs‖2
Well the conditions on m in the hypothesis suffice to apply Lemma C.10 with Γ = e2 ensure that with probability at least 1− δ
sup s≤t ‖(TK∞ − T sn)rs‖2 = Õ
( S
√ d√ m [1 + tS] + S(1 + T ) √ σ1κp√ n
) .
Since κ and σ1 only depend on K∞ which is fixed we will treat them as constants for simplicity of presentation of the main result (note that they were tracked in all previous results for anyone interested in the specific constants). The desired result follows from plugging in the above expression into the previous bounds after setting σ1 and κ as constants.
Theorem 3.5 is strong enough to get a bound on the test error, which is demonstrated by the following corollary. Corollary 3.6. Assume Assumptions 3.3 and 3.4 hold. Suppose that f∗ = O(1) and assume we are performing the doubling trick where f0 ≡ 0 so that r0 = −f∗. Let k ∈ N and let Pk be the orthogonal projection onto span{φ1, . . . , φk}. Set t = log( √ 2‖Pkf∗‖2/ 1/2)
σk Then we have that
m = Ω̃( d σ4k
) and n = Ω̃ (
p σ4k
) suffices to ensure with probability at least 1− δ
1 2 ‖rt‖22 ≤ 2 + 2 ‖(I − Pk)f ∗‖22 .
Proof. Set t = log( √ 2‖Pkf∗‖2/ 1/2)
σk . Note that
1 2 ‖rt‖22 ≤ 1 2 [‖exp(−TK∞t)r0‖2 + ‖rt − exp(−TK∞t)r0‖2] 2
≤ 2 max{‖exp(−TK∞t)r0‖2 , ‖rt − exp(−TK∞t)r0‖2} 2 ≤ 2 [ ‖exp(−TK∞t)r0‖22 + ‖rt − exp(−TK∞t)r0‖ 2 2 ] .
Note that
‖exp(−TK∞t)r0‖22 = ‖exp(−TK∞t)f ∗‖22 = ∞∑ i=1 exp(−2σit)|〈f∗, φi〉2|2
≤ exp(−2σkt) k∑ i=1 |〈f∗, φi〉2|2 + ∞∑ i=k+1 |〈f∗, φi〉2|2
= 2 + ‖(I − Pk)f∗‖22 .
We want to apply Theorem 3.5 with T = t. We need
m ≥ D2 ‖y‖2Rn t 2 and m ≥ O(log(c/δ) + Õ(d)) max{t2, 1}.
Note that since f∗ = O(1) we have that ‖r̂(0)‖Rn = ‖y‖Rn = O(1). Then
D2 ‖y‖2Rn t 2 = Õ
( t2 ) = Õ
( 1
σ2k
) .
thus our condition on m is strong enough to satisfy the first condition. Also O(log(c/δ) + Õ(d)) max{t2, 1} = Õ(dt2) which is satisfied by our condition on m. Thus by an application of Theorem 3.5 with T = t we have with probability at least 1− δ
‖rt − exp(−TK∞t)r0‖2 ≤ tÕ ( ‖f∗‖∞ [1 + t ‖f ∗‖∞] √ d√ m + ‖f∗‖∞ (1 + t) √ p √ n ) .
Recall that f∗ = O(1). Thus the first term above is
Õ ( t2 √ d√ m ) = Õ ( √ d σ2k √ m ) .
Thus setting m = Ω̃( d σ4k
) suffices to ensure the first term is bounded by 1/2/(2 √
2). Similarly the second term is
Õ
( t2 √ p
√ n
) = Õ ( √ p
σ2k √ n
) .
Thus setting n = Ω̃ (
p σ4k
) suffices to ensure that the second term bounded by 1/2/(2 √ 2). Thus in
this case we have
‖rt − exp(−TK∞t)r0‖2 ≤ 1/2√
2 .
Thus we have 1
2 ‖rt‖22 ≤ 2
[ ‖exp(−TK∞t)r0‖22 + ‖rt − exp(−TK∞t)r0‖ 2 2 ] ≤ 2 + 2 ‖(I − Pk)f∗‖22 .

heading: C.8 DETERMINISTIC INITIALIZATION
text: In this section we will prove a version of Theorem 3.5 where instead of θ0 being chosen randomly we take θ0 to be some deterministic value. θ0 could represent the parameters given by the output of some pretraining procedure that is independent of the training data, or selected with a priori knowledge. Lemma C.11. Let θ0 be a fixed parameter initialization. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1},
ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1},
ξ̃(t) = max{max `∈[m] ‖w`(t)‖2 , ‖a(t)‖∞ , ‖b(t)‖∞ , 1}.
Furthermore assume
m ≥ D2 ‖r̂(0)‖2Rn T 2
[log(Γ)]2 .
Then max t∈[0,T ] ξ(t) ≤ Γξ(0) max t∈[0,T ] ξ̃(t) ≤ Γξ̃(0).
Proof. By the hypothesis on m we have that for t ≤ T
D ‖r̂(0)‖Rn t√ m ≤ log Γ.
Therefore by Lemmas B.2 and B.3 the desired result holds.
Lemma C.12. Let θ0 be a fixed parameter initialization. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1},
ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1},
and assume
m ≥ D2 ‖r̂(0)‖2Rn T 2
[log(Γ)]2 .
Then for t ≤ T ‖ft − f∗‖∞ ≤ ‖f0 − f ∗‖∞ + t ‖r̂(0)‖Rn CD 2Γ2ξ(0)2.
Proof. Recall that
∂t(ft(x)− f∗(x)) = − 1
n n∑ i=1 Kt(x, xi)(ft(xi)− f∗(xi)) = − 1 n n∑ i=1 Kt(x, xi)r̂(t)i.
Thus
|∂t(ft(x)− f∗(x))| ≤ 1
n n∑ i=1 |Kt(x, xi)||r̂(t)i| ≤ ‖Kt‖∞ ‖r̂(t)‖Rn ≤ ‖Kt‖∞ ‖r̂(0)‖Rn .
Well by Lemma B.5 we have that ‖Kt‖∞ ≤ CD2ξ2(t). Also by Lemma C.11 we have that
max t∈[0,T ]
ξ(t) ≤ Γξ(0).
Thus by the fundamental theorem of calculus for t ≤ T
|ft(x)− f∗(x)| ≤ |f0(x)− f∗(x)|+ t ‖r̂(0)‖Rn CD 2Γ2ξ(0)2.
Thus by taking the supremum over x we get
‖ft − f∗‖∞ ≤ ‖f0 − f ∗‖∞ + t ‖r̂(0)‖Rn CD 2Γ2ξ(0)2
which is the desired conclusion.
Lemma C.13. Let θ0 be a fixed parameter initialization. Let K0 denote the time-dependent NTK at initialization θ0. Let TK0h(•) = ∫ X K0(•, s)h(s)dρ(s) and Tnh(•) = 1n ∑n i=1K0(•, xi)h(xi) be the associated operators. Let κ = maxxK0(x, x) and let σ1 denote the largest eigenvalue of TK0 . Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1},
ξ(0) = max{ 1√ m ‖W (0)‖op , 1√ m ‖b(0)‖2 , 1√ m ‖a(0)‖2 , 1},
and assume
m ≥ D2 [‖f∗‖∞ + ‖f0‖∞] 2 T 2
[log(Γ)]2 .
Then with probability at least 1− δ over the sampling of x1, . . . , xn we have that
sup t≤T ‖(Tn − TK0)rt‖2 = Õ
( (‖f∗‖∞ + ‖f0‖∞)(1 + TΓ2ξ(0)2) √ σ1κp√
n
) .
Proof. First note that ‖r̂(0)‖Rn ≤ ‖r0‖∞ ≤ ‖f ∗‖∞ + ‖f0‖∞ . (10)
Thus our hypothesis on m is strong enough to apply Lemma C.11 so that we have
max t∈[0,T ]
ξ(t) ≤ Γξ(0) =: A. (11)
Also by Lemma C.5 |b0(t)| ≤ |b0(0)|+ t ‖r̂(0)‖Rn ,
therefore max t≤T |b0(t)| ≤ |b0(0)|+ T ‖r̂(0)‖Rn := B.
Thus up until time T the neural network is in class C as defined in Corollary C.2 with parameters A and B as defined above. Furthermore by Lemma C.12 we have
‖ft − f∗‖∞ ≤ ‖f0 − f ∗‖∞ + t ‖r̂(0)‖Rn CD 2Γ2ξ(0)2.
Well then by (10) and the above we have
‖rt‖∞ ≤ (‖f ∗‖∞ + ‖f0‖∞)
{ 1 + TCD2Γ2ξ(0)2 } =: S.
Thus by an application of Lemma C.3 with K = K0 we have with probability at least 1− δ over the sampling of x1, . . . , xn that
sup t≤T ‖(Tn − TK0)rt‖2 ≤
2 [ 1 + S √ σ1κ √ 2 log(c/δ) + Õ(p) ] √ n
= Õ
( (‖f∗‖∞ + ‖f0‖∞)(1 + TΓ2ξ(0)2) √ σ1κp√
n ) where we have used that S = Õ([‖f∗‖∞ + ‖f0‖∞][1 + TΓ2ξ(0)2]).
Lemma C.14. Let θ0 be a fixed parameter initialization. Let Γ > 1, T > 0, D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}, D′ :=[ max{‖σ′‖∞ , ‖σ′′‖∞}2[M2 + 1] +D ‖σ′‖∞ ] max{1,M},
ξ(t) = max{ 1√ m ‖W (t)‖op , 1√ m ‖b(t)‖2 , 1√ m ‖a(t)‖2 , 1},
ξ̃(t) = max{max `∈[m] ‖w`(t)‖2 , ‖a(t)‖∞ , ‖b(t)‖∞ , 1}.
Furthermore assume
m ≥ D2 ‖r̂(0)‖2Rn T 2
[log(Γ)]2 .
Then for t ≤ T
‖K0 −Kt‖∞ ≤ t CDD′√
m Γ3ξ(0)2ξ̃(0) ‖r̂(0)‖Rn .
Proof. Note by Lemma B.24 we have that
sup x,y∈BM×BM
|∂tKt(x, y)| ≤ CDD′√
m ξ(t)2ξ̃(t) ‖r̂(t)‖Rn .
Now applying Lemma C.11 and the fact that ‖r̂(t)‖Rn ≤ ‖r̂(0)‖Rn from the above we get that for t ≤ T
sup x,y∈BM×BM
|∂tKt(x, y)| ≤ CDD′√
m Γ3ξ(0)2ξ̃(0) ‖r̂(0)‖Rn .
Thus by the fundamental theorem of calculus we have that for t ≤ T
‖K0 −Kt‖∞ ≤ t CDD′√
m Γ3ξ(0)2ξ̃(0) ‖r̂(0)‖Rn .
Theorem C.15. Let θ0 be a fixed parameter initialization. Assume that Assumption 3.3 holds. Let {φi}i denote the eigenfunctions of TK0 corresponding to the nonzero eigenvalues, which we enumerate σ1 ≥ σ2 ≥ · · · . Let Pk be the orthogonal projection in L2 onto span{φ1, . . . , φk} and let D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}. Also let T > 0 and set
ξ(0) = max{ 1√ m ‖W (0)‖op , 1√ m ‖b(0)‖2 , 1√ m ‖a(0)‖2 , 1},
ξ̃(0) = max{max `∈[m] ‖w`(0)‖2 , ‖a(0)‖∞ , ‖b(0)‖∞ , 1}.
S := Õ([‖f∗‖∞ + ‖f0‖∞][1 + Tξ(0) 2]).
Assume m ≥ D2 [‖f∗‖∞ + ‖f0‖∞] 2 T 2. Then with probability at least 1− δ over the sampling of x1, . . . , xn we have that for all t ≤ T and k ∈ N
‖Pk(rt − exp(−TK0t)r0)‖2 ≤ 1− exp(−σkt)
σk Õ ( t√ m ξ(0)2ξ̃(0) ‖r̂(0)‖2Rn + S √ σ1κp√ n ) and
‖rt − exp(−TK0t)r0‖2 ≤ tÕ (
t√ m ξ(0)2ξ̃(0) ‖r̂(0)‖2Rn + S √ σ1κp√ n
) .
Proof. By Lemma C.8 we have for any k ∈ N
‖Pk(rt − exp(−TK0t)r0)‖2 ≤ 1− exp(−σkt)
σk sup s≤t ‖(TK0 − T sn)rs‖2
and furthermore ‖rt − exp(−TK0t)r0‖ ≤ t sup
s≤t ‖(TK0 − T sn)rs‖2 .
Let Tnh(•) = 1n ∑n i=1K0(•, xi)h(xi) be the discretization of TK0 . Thus by Lemma C.9 we have
sup s≤t ‖(TK0 − T sn)rs‖2 ≤ sup s≤t ‖(TK0 − Tn)rs‖2 + sup s≤t ‖K0 −Ks‖∞ ‖r̂(0)‖Rn .
Note from the inequality
‖r̂(0)‖Rn ≤ ‖r0‖∞ ≤ ‖f ∗‖∞ + ‖f0‖∞
the hypothesis onm is strong enough to apply Lemma C.14 with Γ = e. Well then by an application of Lemma C.14 with Γ = e we have that
sup s≤t ‖Ks −K0‖∞ = Õ ( t√ m ξ(0)2ξ̃(0) ‖r̂(0)‖Rn ) .
Separately by Lemma C.13 we have with probability at least 1− δ
sup s≤t ‖(TK0 − Tn)rs‖2 = Õ
( (‖f∗‖∞ + ‖f0‖∞)(1 + Tξ(0)2) √ σ1κp√
n
) .
Combining these results we get that
sup s≤t ‖(TK0 − T sn)rs‖2 ≤ Õ ( t√ m ξ(0)2ξ̃(0) ‖r̂(0)‖2Rn + S √ σ1κp√ n ) .
The desired result follows from plugging in the above expression into the previous bounds.

heading: D DAMPED DEVIATIONS ON TRAINING SET
text: The damped deviations lemma for the training set is incredibly simple to prove and yet is incredibly powerful as we will see later. Here is the proof. Lemma 2.1. Let G ∈ Rn×n be an arbitrary positive semidefinite matrix and let Gs be the time dependent NTK matrix at time s. Then
r̂t = exp(−Gt)r̂0 + ∫ t
0
exp(−G(t− s))(G−Gs)r̂sds.
Proof. Note that we have the equation
∂tr̂t = −Gtr̂t = −Gr̂t + (G−Gt)r̂t.
Thus by multiplying by the integrating factor exp(Gt) and using the fact that exp(Gt) and G commute we have that ∂t exp(Gt)r̂t = exp(Gt)(G−Gt)r̂t. Therefore by the fundamental theorem of calculus
exp(Gt)r̂t − r̂0 = ∫ t
0
exp(Gs)(G−Gs)r̂sds,
which after rearrangement gives r̂t = exp(−Gt)r̂0 + ∫ t
0
exp(−G(t− s))(G−Gs)r̂sds.
Throughout we will let u1, . . . , un denote the eigenvectors of G∞ with corresponding eigenvalues λ1, . . . , λn, normalized to have unit norm in ‖•‖Rn , i.e. ‖ui‖Rn = 1. The following corollary demonstrates that if one is only interested in approximating the top eigenvectors, then the deviations of the NTK only need to be small relative to the cutoff eigenvalue λi that you care about. Corollary D.1. Let Pk be the orthogonal projection onto span{u1, . . . , uk}. Then for any k ∈ [n]
‖Pk(r̂t − exp(−G∞t)r̂0)‖Rn ≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn 1− exp(−λkt) λk
≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn t.
In particular
‖r̂t − exp(−G∞t)r̂0‖Rn ≤ sup s≤t ‖G∞ −Gs‖Rn ‖r̂0‖Rn 1− exp(−λnt) λn ≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn t.
Proof. Note by Lemma 2.1 we have that r̂t − exp(−G∞t)r̂0 = ∫ t
0
exp(−G∞(t− s))(G∞ −Gs)r̂sds
Therefore for any k ∈ [n] Pk(r̂t − exp(−G∞t)r̂0) = Pk ∫ t
0
exp(−G∞(t− s))(G∞ −Gs)r̂sds
= ∫ t 0 Pk exp(−G∞(t− s))(G∞ −Gs)r̂sds
Thus
‖Pk(r̂t − exp(−G∞t)r̂0)‖Rn = ∥∥∥∥∫ t
0 Pk exp(−G∞(t− s))(G∞ −Gs)r̂sds ∥∥∥∥ Rn
≤ ∫ t
0
‖Pk exp(−G∞(t− s))(G∞ −Gs)r̂s‖Rn ds
≤ ∫ t
0
‖Pk exp(−G∞(t− s))‖op ‖G ∞ −Gs‖op ‖r̂s‖Rn ds
≤ ∫ t
0
exp(−λk(t− s)) ‖G∞ −Gs‖op ‖r̂0‖Rn ds
≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn ∫ t 0 exp(−λk(t− s))ds
≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn 1− exp(−λkt) λk
≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn t
where we have used the inequality 1 +x ≤ exp(x) in the last inequality. By specializing to the case k = n since span{u1, . . . , un} = Rn we have
‖r̂t − exp(−G∞t)r̂0‖Rn ≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn 1− exp(−λnt) λn
≤ sup s≤t ‖G∞ −Gs‖op ‖r̂0‖Rn t.
This completes the proof.
Theorem 3.5 uses the concept of damped deviations to compare rt with exp(−TK∞t)r0. We can also prove the analogous statement on the training set that compares r̂t to exp(−G∞t)r̂0. The following is the analog of Theorem 3.5 on the training set.
Theorem D.2. Let D := 3 max{|σ(0)|,M ‖σ′‖∞ , ‖σ′‖∞ , 1}. Also let Γ > 1, T > 0. Furthermore assume
m ≥ 4D2 ‖y‖2Rn T 2
[log(Γ)]2 and m ≥ max
{ 4D2O(log(c/δ) + Õ(d))T 2
[log(Γ)]2 , O(log(c/δ) + Õ(d)) } Let Pk be the orthogonal projection onto span{u1, . . . , uk}. Then with probability at least 1− δ we have for any k ∈ [n] and t ≤ T
‖Pk(r̂t − exp(−G∞t)r̂0)‖Rn ≤ 1− exp(−λkt)
λk ‖r̂0‖Rn Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ])
≤ t ‖r̂0‖Rn Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) in particular
‖r̂t − exp(−G∞t)r̂0‖Rn ≤ 1− exp(−λnt)
λn ‖r̂0‖Rn Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ])
≤ t ‖r̂0‖Rn Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) .
If one instead does the doubling trick the condition 4D 2O(log(c/δ)+Õ(d))T 2
[log(Γ)]2 can be removed from the hypothesis and the same conclusion holds.
Proof. By Corollary D.1 we have
‖Pk(r̂t − exp(−G∞t)r̂0)‖Rn ≤ sup s≤t ‖G∞ −Gs‖Rn ‖r̂0‖Rn 1− exp(−λkt) λk
≤ sup s≤t ‖G∞ −Gs‖Rn ‖r̂0‖Rn t
Well by Theorem B.27 we have with probability at least 1− δ
sup s≤t ‖G∞ −Gt‖op ≤ Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ]) The desired result follows from plugging this in to the previous bounds.

heading: E PROOF OF THEOREM 3.7
text: We can now quickly prove our analog of Theorem 4.1 from Arora et al. (2019).
Theorem 3.7. Assume m = Ω̃(dn5 −2λn(H∞)−4) and m ≥ O(log(c/δ) + Õ(d)) and f∗ = O(1). Assume we are performing the doubling trick so that r̂0 = −y. Let v1, . . . , vn denote the eigenvectors of G∞ normalized to have unit L2 norm ‖vi‖2 = 1. Then with probability at least 1− δ r̂t = exp(−G∞t)(−y) + δ(t), where supt≥0 ‖δ(t)‖2 ≤ . In particular
‖r̂t‖2 = √√√√ n∑ i=1 exp(−2λit)|〈y, vi〉2|2 ± .
Proof. Set T = log(‖r̂(0)‖Rn √ n/ )/λn. Note that since f∗ = O(1) and we are performing the doubling trick we have that ‖r̂0‖Rn = ‖y‖Rn = O(1). Recall that λn := 1 nλn(H
∞) therefore m = Ω̃(dn5 −2λn(H ∞)−4) = Ω̃(dn −2λ−4n ) is strong enough to ensure that
m ≥ 4D2 ‖y‖2Rn T 2
[log(2)]2 = Õ(λ−2n ) m ≥ O(log(c/δ) + Õ(d)) = Õ(d)
Then by an application of Theorem D.2 with Γ = 2 we have with probability at least 1− δ that for all t ≤ T
‖r̂t − exp(−G∞t)r̂0‖Rn ≤ 1− exp(−λnt)
λn ‖r̂0‖Rn Õ ( √ d√ m [ 1 + tΓ3 ‖r̂(0)‖Rn ])
≤ ‖r̂0‖Rn λn Õ ( √ d√ m [ 1 + TΓ3 ‖r̂(0)‖Rn ]) Since f∗ = O(1) we have that ‖r̂0‖Rn = ‖y‖Rn = O(1) therefore the above bound is
Õ ( √ d√ m T
λn
) = Õ ( √ d√ m 1
λ2n ) Thus m = Ω̃(dn5 −2λn(H∞)−4) = Ω̃(dn −2λ−4n ) suffices to make the above term bounded by / √ n. Thus in this case
sup t≤T ‖r̂t − exp(−G∞t)r̂0‖Rn ≤ /
√ n.
Let δ(t) = r̂t − exp(−G∞t)r̂0. We have just shown that supt≤T ‖δ(t)‖Rn ≤ / √ n. We will now bound δ(t) for t ≥ T . Note that for t ≥ T
‖exp(−G∞t)r̂0‖Rn ≤ exp(−λnt) ‖r̂0‖Rn ≤ exp(−λnT ) ‖r̂0‖Rn ≤ / √ n
Also for t ≥ T
‖r̂t‖Rn ≤ ‖r̂T ‖Rn ≤ ‖exp(−G ∞T )r̂0‖Rn + ‖δ(T )‖Rn ≤ 2 /
√ n
where we have used that ‖r̂t‖Rn is nonincreasing for gradient flow. Therefore for t ≥ T
‖δ(t)‖Rn ≤ ‖r̂t‖Rn + ‖exp(−G ∞t)r̂0‖Rn ≤ 3 /
√ n
Thus we have shown sup t≥0 ‖δ(t)‖Rn ≤ 3 / √ n.
The desired result follows from replacing with /3 in the previous argument and using the fact that ‖•‖2 = √ n ‖•‖Rn and r̂0 = −y.

heading: F PROOF OF THEOREM 3.8
text: Using some lemmas that we leave to the following section, we can prove Theorem 3.8 quite quickly using the damped deviations equation and the NTK deviation bounds.

heading: F.1 MAIN THEOREM
text: Theorem 3.8. Assume Assumptions 3.3 and 3.4 hold. Furthermore assume m = Ω̃ ( −2dT 2 ‖f∗‖2∞ (1 + T ‖f∗‖∞)2 ) where T > 0 is a time parameter and m ≥ O(log(c/δ) + Õ(d)) and n ≥ 128κ 2 log(2/δ)
(σk−σk+1)2 . Also assume f ∗ ∈ L∞(X) ⊂ L2(X) and let PTK∞ be the or-
thogonal projection onto the eigenspaces of TK∞ corresponding to the eigenvalue α ∈ σ(TK∞) and higher. Assume that ∥∥(I − PTK∞ )f∗∥∥∞ ≤ ′ for some ′ ≥ 0. Pick k so that σk = α and σk+1 < α, i.e. k is the index of the last repeated eigenvalue corresponding to α in the ordered sequence {σi}i. Also assume we are performing the doubling trick so that r̂(0) = −y. Then we have with probability at least 1− 3δ over the sampling of x1, . . . , xn and θ0 that for t ≤ T
‖r̂t‖Rn ≤ exp(−λkt) ‖y‖Rn + 4κ ‖f∗‖2
√ 10 log(2/δ)
(σk − σk+1) √ n
+ 2 ′ + .
Proof. Recall that we have ‖r̂(0)‖Rn = ‖−y‖Rn ≤ ‖f∗‖∞. Note that m = Ω̃ ( −2dT 2 ‖f∗‖2∞ (1 + T ‖f∗‖∞)2 ) and m ≥ O(log(c/δ) + Õ(d)) are strong enough to ensure
the hypothesis of Theorem D.2 is satisfied with Γ = 2. From now on Γ = 2 = O(1) and will be treated as a constant. Then by Theorem D.2 with probability at least 1− δ we have for t ≤ T
‖r̂t − exp(−G∞t)r̂0‖Rn ≤ T ‖r̂0‖Rn Õ ( √ d√ m [ 1 + TΓ3 ‖r̂(0)‖Rn ]) Thus using the fact from the doubling trick that ‖r̂(0)‖Rn = ‖y‖Rn ≤ ‖f∗‖∞ setting m = Ω̃ ( −2dT 2 ‖f∗‖2∞ (1 + T ‖f∗‖∞)2 ) suffices to ensure that ‖r̂t − exp(−G∞t)r̂0‖Rn ≤ for t ≤ T . Let Pk be the orthogonal projection onto span{u1, . . . , uk}. Well then for t ≤ T
‖r̂t‖Rn ≤ ‖exp(−G ∞t)r̂0‖Rn + ≤ ‖Pk exp(−G ∞t)r̂0‖Rn + ‖(I − Pk) exp(−G ∞t)r̂0‖Rn +
≤ exp(−λkt) ‖r̂0‖Rn + ‖(I − Pk)r̂0‖Rn +
By Theorem F.6 we have with probability at least 1− 2δ over the sampling of x1, . . . , xn that
‖(I − Pk)y‖Rn ≤ 2 ′ +
4κ ‖f∗‖2 √ 10 log(2/δ)
(σk − σk+1) √ n
.
Since we are using the doubling trick we have r̂0 = −y. Thus we have
‖(I − Pk)r̂0‖Rn ≤ 2 ′ +
4κ ‖f∗‖2 √ 10 log(2/δ)
(σk − σk+1) √ n
.
Thus by taking a union bound we have with probability at least 1− 3δ for all t ≤ T
‖r̂t‖Rn ≤ exp(−λkt) ‖r̂0‖Rn + 4κ ‖f∗‖2
√ 10 log(2/δ)
(σk − σk+1) √ n
+ +2 ′ + .
The desired result follows from r̂0 = −y.

heading: F.2 CONTROL OF INITIAL RESIDUAL
text: We will use some of the notation and operator theory from Section C.1 and Section C.2 in this section, thus it is recommended to have read those sections first. Let u1, . . . , un denote the eigenvectors of G∞ normalized to have unit norm in ‖•‖Rn , i.e. ‖ui‖Rn = 1. Let Pk be the orthogonal projection onto span{u1, . . . , uk}. The goal of this section is to upper bound the extent to which the labels y participate in the bottom eigendirections of G∞, i.e. to show that ‖(I − Pk)y‖Rn is small. Let PTK∞ be some projection onto the top eigenspaces of TK∞ . The idea is to show that if ∥∥(I − PTK∞ )f∗∥∥ 2
is small then by picking Pk so that rank(Pk) = rank(PTK∞ ) then ‖(I − Pk)y‖Rn is also small with high probability. The results in this section essentially all appear in the proofs in Su & Yang (2019). We repeat the arguments here for completeness and due to differences in notation and constants.
We use some of the same machinery in (Rosasco et al., 2010). We define operators LH : H → H and Tn : H → H by
THf := ∫ X 〈f,Ks〉HKsdρ(s)
Tnf := 1
n n∑ i=1 〈f,Kxi〉HKxi
Note that TH is equal to TK∞ on H and Tn is simply the operator you get if you replace ρ in the defintion of TH with the empirical measure 1n ∑n i=1 δxi . We define the “restriction” operator Rn : H → Rn by Rnf = [f(x1), f(x2), . . . , f(xn)] T
Note here the domain of Rn is H but in other parts of this paper we will allow Rn to take more general functions as input. Define R∗n : Rn → H by
R∗n(v1, . . . , vn) = 1
n n∑ i=1 viKxi .
It can be seen that 〈R∗nv, f〉H = 〈v,Rnf〉Rn . and thus R∗n is the adjoint of Rn. Using these operators we may write Tn = R ∗ nRn and G
∞ = RnR ∗ n. It will follow that Tn and G
∞ have the same eigenvalues (up to some zero eigenvalues) and their eigenvectors are related. We recall the following result from (Rosasco et al., 2010) (Proposition 9) Theorem F.1. (Rosasco et al., 2010) The following hold
• The operator Tn is finite rank, self-adjoint and positive, and the matrix G∞ is symmetric and semi-positive definite. In particular the spectrum σ(Tn) of Tn has finitely many nonzero elements and they are contained in [0, κ].
• The spectrum of Tn and G∞ are the same up to zero, specifically σ(G∞) \ {0} = σ(Tn) \ {0}. Moreover if λi is a nonzero eigenvalue and ui and vi are the corresponding eigenvector and eigenfunction forG∞ and Tn respectively (normalized to norm 1 in ‖•‖Rn and ‖•‖H respectively), then
ui = 1
λ 1/2 i
Rnvi
vi = 1
λ 1/2 i
R∗nui = 1
λ 1/2 i
1
n n∑ j=1 Kxj (ui)j
where (ui)j is the jth component of the vector ui.
• The following decompositions hold
G∞w = k∑ j=1 λj〈w, uj〉Rnuj
Tnf = k∑ j=1 λj〈f, vj〉Hvj
where k = rank(G∞) = rank(Tn) and both sums run over the positive eigenvalues. {ui}ki=1 is an orthonormal basis for ker(G∞)⊥ and {vi}ki=1 is an orthonormal basis for ker(Tn)⊥.
We will make use of the following lemma from Rosasco et al. (2010, Proposition 6): Lemma F.2. (Rosasco et al., 2010) Let α1 > α2 > . . . > αN > αN+1 be the top N + 1 distinct eigenvalues of TH. Let PTH be the orthogonal projection onto the eigenfunctions of TH corresponding to eigenvalues αN and above. Let PTn be the projection onto the top k eigenvectors of Tn so that k = dim(range(Tn)) = dim(range(TH)). Assume further that
‖TH − Tn‖HS ≤ αN − αN+1
4 .

heading: Then ∥∥PTH − PTn∥∥
text: HS ≤ 2 αN − αN+1 ‖TH − Tn‖HS .
The following lemma will be useful. Lemma F.3. Let f∗ ∈ L2 and let PTH and PTn be defined as in Lemma F.2. Then
n∑ i=k+1 |〈RnPTK∞ f∗), ui〉Rn |2 ≤ ‖f∗‖22 λk+1 σk ∥∥PTH − PTn∥∥2 HS
Proof. We repeat the same proof as in (Su & Yang, 2019) for completeness and to remove confusion that may arise from differences in notation. The proof was originally given in (Rosasco et al., 2010) albeit with a minor error involving missing multiplicative factors. Note that
PTK∞ f∗ = k∑ j=1 〈f∗, φj〉2φj
Therefore
〈RnPTK∞ f∗, ui〉Rn = k∑ j=1 〈f∗, φj〉2〈Rnφj , ui〉Rn .
Applying Cauchy-Schwarz we get
|〈RnPTK∞ f∗, ui〉Rn |2 ≤  k∑ j=1 |〈f∗, φj〉2|2  k∑ j=1 |〈Rnφj , ui〉Rn |2 
≤ ‖f∗‖22 k∑ j=1 |〈Rnφj , ui〉Rn |2.
Well then note that k∑ j=1 |〈Rnφj , ui〉Rn |2 = k∑ j=1 |〈φj , R∗nui〉H|2 = k∑ j=1 λi|〈φj , vi〉H|2.
Therefore n∑
i=k+1
|〈RnPTK∞ f∗), ui〉Rn |2 ≤ ‖f∗‖22 n∑
i=k+1 k∑ j=1 λi|〈φj , vi〉H|2
≤ ‖f∗‖22 λk+1 n∑
i=k+1 k∑ j=1 |〈φj , vi〉H|2 (12)
On the other hand ∥∥PTH − PTn∥∥2 HS ≥ k∑ j=1 ∥∥(PTH − PTn)√σjφj∥∥2H ≥
k∑ j=1 n∑ i=k+1 |〈(PTH − PTn)√σjφj , vi〉H|2.
Note that for 1 ≤ j ≤ k and k + 1 ≤ i ≤ n we have
〈(PTH − PTn)√σjφj , vi〉H = 〈PTH √ σjφj , vi〉H − 〈PTn √ σjφj , vi〉H
= 〈√σjφj , vi〉H − 〈 √ σjφj , P Tnvi〉H = 〈 √ σjφj , vi〉H.
So k∑ j=1 n∑ i=k+1 |〈(PTH − PTn)√σjφj , vi〉H|2 = k∑ j=1 n∑ i=k+1 |〈√σjφj , vi〉H|2
≥ σk k∑ j=1 n∑ i=k+1 |〈φj , vi〉H|2
To summarize we have shown
1
σk
∥∥PTH − PTn∥∥2 HS ≥ k∑ j=1 n∑ i=k+1 |〈φj , vi〉H|2.
Combining this with (12) we get the final result n∑
i=k+1
|〈RnPTK∞ f∗), ui〉Rn |2 ≤ ‖f∗‖22 λk+1
σk
∥∥PTH − PTn∥∥2 HS .
We can use Lemma F.3 to produce the following bound. Lemma F.4. Let f∗ ∈ L2 and let PTH and PTn be defined as in Lemma F.2. Then
n∑ i=k+1 |〈Rnf∗, ui〉Rn |2 ≤ 2 n n∑ i=1 |(I − PTK∞ )f∗(xi)|2 + 2 ‖f∗‖22 λk+1 σk ∥∥PTH − PTn∥∥2 HS .
Proof. We have that
〈Rnf∗, ui〉Rn = 〈Rn(I − PTK∞ )f∗, ui〉Rn + 〈RnPTK∞ f∗, ui〉Rn .
Thus from the inequality (a+ b)2 ≤ 2(a2 + b2) we get n∑
i=k+1
|〈Rnf∗, ui〉Rn |2 ≤ 2 n∑
i=k+1
|〈Rn(I − PTK∞ )f∗, ui〉Rn |2 + 2 n∑
i=k+1
|〈RnPTK∞ f∗, ui〉Rn |2.
To control the first term we have n∑
i=k+1
|〈Rn(I − PTK∞ )f∗, ui〉Rn |2 ≤ ∥∥(I − PTK∞ )f∗∥∥2Rn = 1n n∑ i=1 |(I − PTK∞ )f∗(xi)|2.
Then by applying Lemma F.3 to the second term we get the desired result.
We recall the following lemma from Rosasco et al. (2010, Theorem 7) Lemma F.5. (Rosasco et al., 2010) With probability at least 1− δ over the sampling of x1, . . . , xn
‖TH − Tn‖HS ≤ 2κ √
2 log(2/δ)√ n .
Now finally we can provide a bound on the labels participation in the bottom eigendirections. Theorem F.6. Assume f∗ ∈ L2(X) and let PTK∞ be the orthogonal projection onto the eigenspaces of TK∞ corresponding to the eigenvalue α ∈ σ(TK∞) and higher. Assume that∥∥(I − PTK∞ )f∗∥∥∞ ≤ ′ for some ′ ≥ 0. Pick k so that σk = α and σk+1 < α, i.e. k is the index of the last repeated eigenvalue corresponding to α in the ordered sequence {σi}i. Let Pk denote the orthogonal projection onto span{u1, . . . , uk}. Finally assume
n ≥ 128κ 2 log(2/δ)
(σk − σk+1)2 .
Then we have with probability at least 1− 2δ over the sampling of x1, . . . , xn that
‖(I − Pk)Rnf∗‖Rn = ‖(I − Pk)y‖Rn ≤ 2 ′ +
4κ ‖f∗‖2 √ 10 log(2/δ)
(σk − σk+1) √ n
.
Proof. From Lemma F.4 we have n∑
i=k+1
|〈Rnf∗, ui〉Rn |2 ≤ 2
n n∑ i=1 |(I − PTK∞ )f∗(xi)|2 + 2 ‖f∗‖22 λk+1 σk ∥∥PTH − PTn∥∥2 HS
By assumption we have that the first term is bounded by 2( ′)2. Now we must control the term
2 ‖f∗‖22 λk+1
σk
∥∥PTH − PTn∥∥2 HS .
By Lemma F.5 we have with probability at least 1− δ ‖TH − Tn‖HS ≤ 2κ √
2 log(2/δ)√ n .
Then
n ≥ 128κ 2 log(2/δ)
(σk − σk+1)2
suffices so that the right hand side above is less than or equal to σk−σk+14 . Thus by Lemma F.2 we have that ∥∥PTH − PTn∥∥
HS ≤ 2 σk − σk+1 ‖TH − Tn‖HS ≤ 2 σk − σk+1 2κ √ 2 log(2/δ)√ n .
Thus from the above inequality we get that
2 ‖f∗‖22 λk+1
σk
∥∥PTH − PTn∥∥2 HS ≤ 64κ2 ‖f∗‖22 λk+1 log(2/δ) σk(σk − σk+1)2 · n .
By Proposition 10 in Rosasco et al. (2010) we have separately with probability at least 1− δ λk+1 ≤ σk+1 + 2κ √
2 log(2/δ)√ n .
Note that
n ≥ 128κ 2 log(2/δ)
(σk − σk+1)2 implies that
1√ n ≤ σk − σk+1 8κ √ 2 log(2/δ) ,
therefore
λk+1 ≤ σk+1 + 2κ √
2 log(2/δ)√ n ≤ σk + 1 4 (σk − σk+1) ≤ 5 4 σk.
Thus
2 ‖f∗‖22 λk+1
σk
∥∥PTH − PTn∥∥2 HS ≤ 64κ2 ‖f∗‖22 λk+1 log(2/δ) σk(σk − σk+1)2n ≤ 80κ2 ‖f∗‖22 log(2/δ) (σk − σk+1)2n .
Thus combined with our previous results we finally get that
‖(I − Pk)Rnf∗‖2Rn = n∑
i=k+1
|〈Rnf∗, ui〉Rn |2 ≤ 2( ′)2 + 80κ2 ‖f∗‖22 log(2/δ)
(σk − σk+1)2n
Thus from the inequality √ a+ b ≤ √ 2( √ a+ √ b) which holds for all a, b ≥ 0 we have
‖(I − Pk)Rnf∗‖Rn ≤ 2 ′ +
4κ ‖f∗‖2 √ 10 log(2/δ)
(σk − σk+1) √ n
.
Since y = Rnf∗ this provides the desired conclusion.

heading: G TK∞ IS STRICTLY POSITIVE
text: Note that
K∞(x, x′) = E[σ(〈w, x〉2+b)σ(〈w, x′〉2+b)]+E[a2σ′(〈w, x〉2+b)σ′(〈w, x′〉2+b)][〈x, x′〉2+1]+1 where the expectation is taken with respect to the parameter initialization. It suffices to show that the kernel corresponding to the first term above
Ka(x, x ′) := E[σ(〈w, x〉2 + b)σ(〈w, x′〉2 + b)] induces a strictly positive operator TKaf(x) = ∫ X Ka(x, s)f(s)dρ(s). From the discussion in Section C.1 it suffices to show that the RKHS corresponding to Ka is dense in L2. In Proposition 4.1 in Rahimi & Recht (2008a) they showed that the RKHS associated with Ka has dense subset
F := { x 7→ ∫ Θ a(w, b)σ(〈w, x〉2 + b)dµ(w, b) : ∫ Θ |a(w, b)|2dµ(w, b) <∞ }
where µ is the measure for the parameter initialization, i.e. (w, b) ∼ µ. Since C(X) is dense in L2(X) it suffices to show that F is dense in C(X) which is provided by the following theorem:
Theorem G.1. Let σ be L-Lipschitz and not a polynomial. Assume that µ is a strictly positive measure supported on all of Rd+1. Also assume that∫
Rd+1 [‖w‖22 + ‖b‖ 2 2]dµ(w, b) <∞.
Then F is dense in C(X) under the uniform norm.
Proof. We first show that F ⊂ C(X). Suppose we have f ∈ F and write f(x) =∫ Rd+1 a(w, b)σ(〈w, x〉2 + b)dµ(w, b). Well then
|f(x)− f(x′)| = ∣∣∣∣∫
Rd+1 a(w, b)[σ(〈w, x〉2 + b)− σ(〈w, x′〉2 + b)]dµ(w, b) ∣∣∣∣ ≤ ∫ Rd+1 |a(w, b)||σ(〈w, x〉2 + b)− σ(〈w, x′〉2 + b)|dµ(w, b)
≤ ∫ Rd+1 |a(w, b)|L|〈w, x− x′〉|dµ(w, b) ≤ ∫ Rd+1 |a(w, b)|L ‖w‖2 ‖x− x ′‖2 dµ(w, b)
≤ L ‖x− x′‖2 [∫ Rd+1 |a(w, b)|2dµ(w, b) ]1/2 [∫ Rd+1 ‖w‖22 dµ(w, b) ]1/2 .
Thus f is Lipschitz and thus continuous. Now suppose that F is not dense in C(X). Then by the Riesz representation theorem there exists a nonzero signed measure ν(x) with finite total variation such that ∫ X f(x)dν(x) = 0 for all f ∈ F . Well then writing f(x) = ∫ Rd+1 a(w, b)σ(〈w, x〉2 + b)dµ(w, b) as before we have∫ X ∫ Rd+1 a(w, b)σ(〈w, x〉2 + b)dµ(w, b)dν(x) = 0 (13) Note that ∫ Rd+1 |a(w, b)||σ(〈w, x〉2 + b)|dµ(w, b)
≤ ∫ Rd+1 |a(w, b)|[|σ(0)|+ L|〈w, x〉2 + b|]dµ(w, b)
≤ ∫ Rd+1 |a(w, b)|[|σ(0)|+ L(‖w‖2M + ‖b‖2)]dµ(w, b) <∞
where we have used Cauchy-Schwarz and the hypothesis on the integrability of ‖w‖22 , ‖b‖ 2 2 in the last step. Thus the integrand in (13) is µ×ν integrable thus by Fubini’s theorem we may interchange the order of integration. To get that∫
Rd+1 a(w, b) ∫ X σ(〈w, x〉2 + b)dν(x)dµ(w, b)
and the above holds for any a ∈ L2(Rd+1, µ). Thus ∫ X σ(〈w, x〉2 +b)dν(x) = 0 for µ-almost every
w, b. However by essentially the same proof as when we showed F ⊂ C(X) we may show that∫ X σ(〈w, x〉2 + b)dν(x) = 0 is a continuous function of (w, b). Thus since µ is a strictly positive
measure on Rd+1 this implies that ∫ X σ(〈w, x〉2 + b)dν(x) = 0 for every (w, b) ∈ Rd+1. However by Theorem 1 in Leshno et al. (1993) we have that span{σ(〈w, x〉2 + b) : (w, b) ∈ Rd+1} is dense in C(X). However by our previous conclusion and linearity we have that ∫ g(x)dν(x) = 0 for any g in span{σ(〈w, x〉2 +b) : (w, b) ∈ Rd+1}, which implies then that ν must equal 0. Thus F is dense in C(X).
Since Gaussians are supported on all of Rd+1 we have the following corollary: Corollary G.2. If (w, b) ∼ N(0, Id+1) then K∞ is strictly positive.

Review summaries:
This work studies the implicit bias of optimizing underparametrized neural networks with MSE loss function and establishes upper-bounds on the training error. One of the takeaways of the paper is that under-parametrized neural networks first learn the most important eigenfunctions associated with the NTK integral operator. This is what the work posits as the implicit bias of gradient-descent in this setting. A key tool developed in the paper is the concept of damped deviations, where in the evolution of MSe w.r.t to one kernel is related to that of another kernel and the damped "distance" between these kernels. As a byproduct, the paper uses this tool to extend certain results in the literature in the over-parametrized setting.

In this paper, the authors study gradient flow on the empirical squared loss. More specifically, they consider the evolution in function space of the residuals and show that it can be written as the sum of 1) the residual obtained by training with the NTK operator (infinite width and samples, no training of the kernel), and 2) damped deviations between time dependent kernel matrix and the NTK operator. Based on this decomposition and a uniform deviation bound on the NTK, they show that 1) in the underparametrized regime, GD at the beginning of the dynamics learn eigenfunctions of NTK at rates proportional to the corresponding eigenvalues; 2) in the overparametrized regime, they derive new bounds for the `kernel regime’ to appear; 3) in the overparametrized regime, if we further assume that the target function is aligned with the top eigenvectors of the NTK, then a milder overparametrization is required.

In the paper under review, the authors study the behaviour of gradient flow in the kernel regime of one hidden layer neural networks. More precisely, they show deviations bounds on the test error  w.r.t. the true NTK gradient flow in the underparametrized regime and train error bounds in the overparametrized regime.