Title: NEURAL TANGENT KERNELS, TRANSPORTATION MAP-PINGS, AND UNIVERSAL APPROXIMATION

Abstract: This paper establishes rates of universal approximation for the shallow neural tangent kernel (NTK): network weights are only allowed microscopic changes from random initialization, which entails that activations are mostly unchanged, and the network is nearly equivalent to its linearization. Concretely, the paper has two main contributions: a generic scheme to approximate functions with the NTK by sampling from transport mappings between the initial weights and their desired values, and the construction of transport mappings via Fourier transforms. Regarding the first contribution, the proof scheme provides another perspective on how the NTK regime arises from rescaling: redundancy in the weights due to resampling allows individual weights to be scaled down. Regarding the second contribution, the most notable transport mapping asserts that roughly 1 /δ 10d nodes are sufficient to approximate continuous functions, where δ depends on the continuity properties of the target function. By contrast, nearly the same proof yields a bound of 1 /δ 2d for shallow ReLU networks; this gap suggests a tantalizing direction for future work, separating shallow ReLU networks and their linearization.

1. MAIN RESULT AND OVERVIEW:

Consider functions computed by a single ReLU layer, meaning

x → m j=1 s j σ w j , x + b j ,

(1.1)

where σ(z) := max{0, z}. While shallow networks are celebrated as being universal approximators (Cybenko, 1989; Funahashi, 1989; Hornik et al., 1989) -they approximate continuous functions arbitrarily well over compact sets -what is more shocking is that gradient descent can learn the parameters to these networks, and they generalize (Zhang et al., 2016) .

Working towards an understanding of gradient descent on shallow (and deep!) networks, researchers began investigating the neural tangent kernel (NTK) (Jacot et al., 2018; Du et al., 2018; Allen-Zhu et al., 2018) , which replaces a network with its linearization at initialization, meaning

x → √ m m j=1 s j τ j , x σ wj , x , where x = (x, 1) ∈ R d+1 , w = (w, b) ∈ R d+1 ; (1.2)

here each wj = (w j , b j ) is frozen at Gaussian initialization (henceforth the bias is collapsed in for convenience), and each transported weight τ j is microscopically close to the corresponding initial weight wj , concretely τ j -wj = O( 1 / √ m), where > 0 is a parameter and the scaling / √ m is conventional in this literature (Allen-Zhu et al., 2018) .

As eq. (1.2) is merely affine in the parameters, it is not outlandish that gradient descent can be analyzed. What is outlandish is firstly that gradient descent on eq. (1.1) with small learning rate will track the behavior of eq. (1.2), and secondly the weights hardly change as a function of m, specifically τ j -wj 2 = O( 1 / Contributions. This work provides rates of function approximation for the NTK as defined in eq. (1.2), moreover in the "NTK setting": the transported weights must be near initialization, meaning τ j -wj = O( 1 / √ m). In more detail:

Continuous functions (cf. Theorem 1.5). The main theorem packages the primary tools here to say: the NTK can approximate continuous functions arbitrarily well, so long as the width is at least 1 /δ 10d , where δ depends on continuity properties of the target function; moreover, the transports satisfy τ j -wj = O( 1 / √ m), and the ReLU network (eq. (1.1)) and its linearization (eq. (1.2)) stay close. Re-using many parts of the proof, a nearly-optimal rate 1 /δ 2d is exhibited for ReLU networks in Theorem E.1; this gap between ReLU networks and their NTK poses a tantalizing gap for future work. Approximation via sampling of transport mappings. The first component of the proof of Theorem 1.5, detailed in Section 2, is a procedure which starts with an infinite width network, and describes how sampling introduces redundancy in the weights, and automatically leads to the desired microscopic transports τ j -wj = O( 1 / √ m). As detailed in Theorem 2.1, the error between the infinite width and sampled networks is O( + 1 / √ m). In this way, the analysis provides another perspective on the scaling behavior and small weight changes of the NTK. Construction of transport mappings. The second component of the proof of Theorem 1.5, detailed in Section 3, is to construct explicit transport mappings for various types of functions. As detailed in Lemma 3.3, approximating continuous functions proceeds by constructing an infinite width network not directly for the target function f , but instead its convolution f * G α with a Gaussian G α with tiny variance α 2 . Care is needed in order to obtain a rate of the form 1 /δ O(d) , rather than, say, 1 /δ O(d/δ) . The main constructions are based on Fourier transforms.

Rounding out the organization of this paper: this introduction will state the main summarizing result and its intuition, and then close with related work; Section 4 will describe certain odds and ends for approximating continuous functions which were left out from the main tools in Section 2 and Section 3; Section 5 sketches abstract approaches to constructing transport mappings, including ones based on a corresponding Hilbert space; Section 6 will conclude with open problems and related discussion. Proofs are sketched in the paper body, but details are deferred to the appendices.

1.1. BASIC NOTATION, INTUITION, AND MAIN RESULT:

The NTK views networks as finite width realizations of intrinsically infinite width objects. In order to transport an infinite number of parameters away from their initialization, one option is to use a transport mapping T : R d+1 → R d+1 to show where weights should go:

x → E w T ( w), Φ(x; w) = E w T ( w), x σ ( w, x ) = E w T ( w), x 1 w, x ≥ 0 , where Φ(x; w) = xσ ( w, x ) is a random feature representation of x (Rahimi & Recht, 2008) . This abstracts the individual transported weights (τ j ) m j=1 from before into transported weights defined over arbitrary weights w ∈ R d+1 . These (augmented) weights w = (w, b) (with weight w ∈ R d and bias b ∈ R) will always be distributed according to a standard Gaussian with identity covariance, with G denoting the density and probability law simultaneously.

A key message of this work, developed in Section 2, is (a) the infinite width network can be sampled to give rates of approximation by finite width networks, (b) the microscopic adjustments of the NTK setting arise naturally from the sampling process! Indeed, letting s ∈ {-1, +1} denote a uniformly distributed random sign,

E w T ( w), Φ(x; w) = E w,s s 2 T ( w) + s w √ m, Φ(x; w) ∵ E s 2 = 1, E s = 0 ≈ 1 m m j=1 s 2 j T ( wj ) + s j wj √ m, Φ(x; wj ) sampling (w j , s j ) = √ m m j=1 s j T ( wj ) √ m + wj , s j Φ(x; wj ) . (1.3)

As highlighted by the bolded terms: increasing the width m corresponds to resampling, and allows the transported weights to be scaled down! Indeed, the distance moved is O( 1 / √ m) by construction. To this end, for convenience define

τ j := T ( wj , s j ) := s j T ( wj ) √ m + wj 1[ wj ≤ R], φ j (x) := Φ (x; wj , s j ) := s j √ m Φ(x; wj ) = s j √ m xσ ( wj , x ), (1.4)

where R is a truncation radius included for purely technical reasons. The transport mappings constructed in Section 3 satisfy B := sup w T ( w) < ∞, and thus max j τ j -wj ≤ B / √ m by construction as promised (with high probability).

The key message of Section 2 is to control the deviations of this process, culminating in Theorem 2.1 and also Theorem 1.5 below, which yields upper bounds on the width necessary to approximate infinite width networks. The notion of approximation here will follow (Barron, 1993) and use the L 2 (P ) metric, where P is a probability measure on the ball {x ∈ R d : x ≤ 1}:

h L2(P ) = h(x) 2 dP (x).

Additionally h L2 = h(x) 2 dx and h L1 = |h(x)| dx will respectively denote the usual L 2 and L 1 metrics over functions on R d . Theorem 1.5 (Simplification of Theorems 2.1 and 4.3). Let continuous function f : R d → R be given, along with δ ∈ (0, 1] so that |f (x)-f (x )| ≤ whenever x-x 2 ≤ δ and max{ x , x } ≤ 1+δ.

Let P be any probability distribution over x ≤ 1. Then there exists a transport mapping T (defining T and τ j as in eq. (1.4)) and associated scalars

B := sup w T ( w) 2 = O M 5 d (5d+9)/2 4 δ 5(d+1)

, where M := sup

x ≤1+δ |f (x)|,

so that with probability at least 1 -3η over Gaussian weights ( wj ) m j=1 and uniform signs (s j ) m j=1 , then max j τ j -wj ≤ B / √ m, and

f - m j=1 τ j , φ j (•) L 2 (P ) ≤ O B √ m + √ d ln(1/η) , √ m m j=1 s j σ( τ j , x ) - m j=1 τ j , φ j (•) L2(P ) ≤ O   B 2 m 3/2 + B √ d m + B √ m + √ d ln(1/η)   .

In words: given an arbitrary target function f and associated continuity parameter δ, width (B/ ) 2 = O( d 5d+9 / 10 δ 10(d+1) ) suffices for error O( ), parameters are close to initialization, and the NTK and the original network behave similarly. The randomized construction does not merely give existence, but holds with high probability: the sampling process is thus in a sense robust, and may be used algorithmically!

As provided in Theorem 4.5, elements of the proof of Theorem 1.5 can be extracted and converted into a direct approximation rate of continuous functions by ReLU networks, and the rate becomes O( d d+2 / 2 δ 2d+2 ). Since this rate is nearly tight, together these rates pose an interesting question: is there a purely approximation-theoretic gap between shallow ReLU networks and their NTK?

1.2. RELATED WORK:

Optimization literature; the NTK. This work is motivated and inspired by the optimization literature, which introduced the NTK to study gradient descent in a variety of nearly-parallel works (Jacot et al., 2018; Du et al., 2018; Du et al., 2018; Allen-Zhu et al., 2018; Arora et al., 2019; Oymak & Soltanolkotabi, 2019; Li & Liang, 2018; Cao & Gu, 2019) . These works require the network width to be polynomial in n, the size of the training set; by contrast, the analysis here studies closeness in function space, and the width instead scales with properties of the target function.

One close relative to the present work is that of (Chizat & Bach, 2019) , which provides an abstract proof scheme following the preceding works, and explains the microscopic change of the weights as a consequence of the scaling / √ m. This is consistent with the resampling perspective here, as summarized in eq. (1.3).

Random features and the mean-field perspective. The random features perspective (Rahimi & Recht, 2008 ) studies a related convex problem: similarly to the NTK, the activations σ ( wj , x ) are held fixed, and what are trained are scalar weights a j ∈ R on each feature. The Fourier transport map construction used both for the NTK here in Theorem 1.5 and for shallow networks in Theorem E.1 proceeds by constructing exactly such a reweighting, and thus the present work also establishes universal approximation properties of random features. A related perspective is presented in the mean-field literature, which relate gradient descent on ( wj ) m j=1 to a Wasserstein flow in the space of distributions on these features (Chizat & Bach; Mei et al., 2018) . The analysis here does not have any explicit ties to the mean-field literature, however it is interesting and suggestive that transport mappings appear in both.

Approximation literature. The closest prior work is due to Barron (1993) , who gave good rates of approximation for functions f : R d → R when the associated quantity w • | f (w)| dw is small, where f denotes the Fourier transform of f . The proofs in Section 3 will use elements from the proofs in (Barron, 1993) , but with many distinct components, and thus it is interesting that the same quantity w • | f (w)| dw arises once again. Like the work of (Barron, 1993) , the present work also chooses to approximate in the L 2 (P ) metric. Standard classical works in this literature are general universal approximation guarantees without rates or attention to the weight magnitudes (Cybenko, 1989; Hornik et al., 1989; Funahashi, 1989; Leshno et al., 1993) . The rate given here of roughly 1 /δ 2d in Theorem 4.5 does not seem to appear rigorously in prior work, though it is mentioned as a consequence of a proof in (Mhaskar & Micchelli, 1992) , who also take the approach of approximation via Gaussian convolutions; the use of convolutions is not only standard (Wendland, 2004) , it is moreover classical, having been used in Weierstrass's original proof (Weierstrass, 1885) .

Many related works use a RKHSes directly. Sun et al. (2018) prove universal approximation (with rates) via an RKHS, however they do not consider the NTK (or the NTK setting of small weight changes). Bach (2017a) (see also (Bach, 2017b; Basri et al., 2019; Bietti & Mairal, 2019) ) studies a variety of questions related to function fitting with the random features model, including establishing rates of approximation for Lipschitz functions on the surface of the sphere (with a few further conditions); the rates are better than those here (roughly Θ( 1 /δ d/2 )), however they do not consider the NTK setting, meaning either the setting of small changes from initialization nor the linearization.

Another close parallel work studies exact representation power of infinite width networks, developing representations for functions with Ω(d) derivatives (Ongie et al., 2019) ; similarly, the constructions here use an exact representation result for Gaussian convolutions, as developed in Section 3.

Regarding lower bounds from the literature, there are two lower bounds of the form 1 /δ d/2 for general shallow networks, not necessarily in the NTK setting (Yarotsky, 2016; Bach, 2017a) . Interestingly, Yarotsky (2016) also presents a lower bound of 1 /δ d for approximations whose parameters vary continuously with the target function; this seems to hold for the Fourier constructions here in Section 3, though an argument needs to be made for the sampling step.

2. SAMPLING FROM A TRANSPORT:

This section establishes that by sampling from an infinite width NTK, the resulting finite width NTK is close in L 2 (P ) both to the infinite width idealization, and also to the finite width non-linearized ReLU network; moreover, the sampling process introduces redundancy in the weights, allowing them to be scaled down and lie close to initialization.

Theorem 2.1. Suppose B ≥ max 2, sup w T ( w) 2 , and set R := √ d + 1 + 2 ln(m/η). With probability at least 1 -3η, then max j τ j -wj ≤ B / √ m, and

m j=1 τ j , φ j (•) -E w T ( w), Φ(•; w) L 2 (P ) ≤ 2 B √ m + R 1 + ln(1/η) , (2.2) j τ j , φ j (•) - j s j √ m σ( τ j , • ) L2(P ) ≤ 2 B 2 m 3/2 + BR m + B √ m + R 1 + ln(1/η) .

(2.3)

As discussed in the introduction, max j τ j -wj ≤ B / √ m is essentially by construction. Next, recall the sampling derivation in eq. (1.3), restated here as a lemma for convenience, the notation (W, S) collecting all random variables together, meaning W = ( w1 , . . . , wm ) and S = (s 1 , . . . , s m ).

Lemma 2.4.

E w T ( w), Φ(x; w) = E W ,S j T ( wj , s j ), Φ (x; wj , s j ) = E W ,S j τ j , φ j (x) .

The proof of eq. (2.2) now follows from the classical Maurey sampling lemma (Pisier, 1980) , which was also used in the related work by Barron (1993) . The following version additionally includes a high probability control, which results from an application of McDiarmid's inequality. Applying the following sampling lemma to the present setting, the deviations will scale with B := sup w T ( w) 2 . Lemma 2.5 (Maurey). Let functions {g(•; v) : v ∈ V} be given, where V ⊆ R p is a set of possible parameters. Let ν be a probability measure over V, let (v 1 , . . . , v m ) be an iid random draw from ν, and define

f (x) := E v∼ν g(x; v) and g j (x) := g(x; v j ).

Then

E ((sj ,vj )) m j=1 f - 1 m m j=1 g j 2 L 2 (P ) ≤ 1 m E v g(•; v) 2 L2(P ) ≤ 1 m sup v∈V g(•; v) 2 L2(P ) ,

and with probability at least

1 -η, f - 1 m m j=1 g j L 2 (P ) ≤ sup v∈V g(•; v) L2(P ) 1 + 2 ln(1/η) √ m .

Concretely, here g j (x) = m τ j , φ j (x) , and sup v∈V g(•; w)

L2(P ) ≤ √ 2 sup w T ( w) 2 = O(B + R √ m)

by Cauchy-Schwarz. Before continuing, note also that there are other proof schemes attaining similar bounds (Bach, 2017a ;b, Proposition 1), and that similar bounds are possible for the uniform norm, albeit with more sensitivity to the basis functions g (cf. Lemma B.2).

Turning now to the final bound in eq. ( 2.3), the first step is to note by positive homogeneity of the ReLU that σ( τ

j , x ) = τ j , x σ ( τ j , x ), thus m j=1 τ j , φ j -√ m m j=1 s j σ( τ j , x ) = m j=1 τ j , φ j - s j √ m xσ ( τ j , x ) ,

which boils down to checking the difference in activations, namely σ ( wj , x ) -σ ( τ j , x ). As is standard in the NTK literature, since τ j -wj is (with high probability) microscopic compared to wj , x , the activations should also be close. The following lemma makes this precise.

Lemma 2.6. For any

x ∈ R p , if R ≥ √ d + 2 ln √ mπ B √ 2

(as used in eq. (1.4)), then

E w σ ( w, x ) -σ ( T ( w), x ) ≤ 2B √ 2 √ mπ .

From here, the eq. ( 2.3) can be established with another application of Lemma 2.5. This completes the proof of Theorem 2.1 after an application of Gaussian concentration to ensure max j wj ≤ R. This also establishes the first half of Theorem 1.5.

3. CONCRETE TRANSPORT MAPPINGS VIA FOURIER TRANSFORMS:

The previous section showed function approximation in the NTK setting assuming the existence of an infinite width NTK defined by a transport mapping T ; this section will close the gap by providing a variety of transport maps.

The transport mappings here will be constructed via Fourier transforms, with convention

f (x) = exp -2πix T w f (x) dx;

a few general properties are summarized in Appendix A. Interestingly, these transports are all random feature transports: they have the form

T ( w) = (0, • • • , 0, p( w))

where p is a signed density over random features, and E w T ( w), Φ(x; w) = E wp( w)σ ( w, x ). This perspective of a signed density will be used to prove universal approximation -again via sampling! -of shallow ReLU networks (and random features) later in Theorems 4.5 and E.1. (For constructions which are not based on random features, see Section 5.)

The first steps of the approach here follow a derivation due to Barron (1993) . Specifically, the inverse Fourier transform gives a way to rewrite a function as an infinite with network with complex-valued activations x → exp(2πix T w):

f (x) = exp(2πix T w) f (w) dw.

A key trick due to Barron (1993) is to force the right hand side to be real (since the left hand side is real): specifically, letting

f (w) = | f (w)| exp(2πiθ f (w)) with |θ f (w)| ≤ 1 denote the radial decomposition of f , Ref (x) = Re exp(2πix T w) f (w) dw = Re exp(2πix T w + 2πiθ f (w))| f (w)| dw = cos 2π(x T w + θ f (w)) | f (w)| dw.

After this step, the proofs diverge: the approach here is to use the fundamental theorem of calculus to rewrite cos in terms of σ :

cos(z) -cos(0) = - z 0 sin(b) db = - ∞ 0 sin(b)1[z -b ≥ 0] db, = - ∞ 0 sin(b)σ (z -b) db;

plugging this back in gives an explicit representation of f in terms of an infinite width threshold network! A similar approach can be used to obtain an infinite width ReLU network. This is summarized in the following lemma, which includes a calculation of the error incurred by truncating the weights; this truncation is necessary when applying the sampling of Section 2. Interestingly, this truncation procedure leads to the quantity w • | f (w)| dw, which was explicitly introduced as a key quantity by Barron (1993) via a different route, namely of introducing a factor w to enforce decay on cos. 1. Define infinite width threshold network

F r (x) := f (0) + | f (w)| cos 2π(θ f (w) -w ) dw + 2π σ ( w, x )| f (w)| sin(2π(θ f (w) -b))1[|b| ≤ w ≤ r] d w. For any x ≤ 1, F ∞ = f and f (x) -F r (x) ≤ 4π w >r w • | f (w)| dw. 2. Define infinite width ReLU network Q r (x) := f (0) + | f (w)| cos(2π(θ f (w) -w )) -2π w sin(2π(θ f (w) -w )) dw + x T w| f (w)| dw + 4π 2 σ( wT x)| f (w)| cos(2π( w -b))1[|b| ≤ w ≤ r] d w. For any x ≤ 1, Q ∞ = f and f (x) -Q r (x) ≤ 12π 2 w >r w 2 • | f (w)| dw.

(The second part of the shows that the same technique allows functions to be written with equality as ReLU networks; this is included as a curiosity and used in a few places in the appendices, but is not part of the main NTK story.)

The preceding constructions immediately yield transport mappings from Gaussian initialization to the function f in a brute-force way: by introducing the fraction G( w) /G( w), calling the numerator part of the integration measure, and the denominator part of the integrand. As stated before, these transport maps are random feature maps: they zero out the coordinates corresponding to x! Lemma 3.2. Let f : R d → R be given with Fourier transform f . For any r ∈ [0, ∞], define transport mapping T r (w, b) := (0, . . . , 0, p r ( w)) with

T r (w, b) d+1 = p r ( w) := 2 f (0) + | f (v)| cos(2π(θ f (v) -v )) dv + 2π | f (w)| G( w) cos(2π(θ f (w) -b))1[|b| ≤ w ≤ r].

By this choice, for any x ≤ 1, f (x) = E w T ∞ ( w), Φ(x; w) , and

sup w T r ( w) 2 ≤ 2 f (0) + 2 | f (v)| dv + 2π sup w ≤r |b|≤ w | f (w)| G( w) , f (x) -E T ( w), Φ(x; w) ≤ 4π w >r | f (w)| • w dw.

The preceding construction may seem general, however it is quite loose, noting the final supremum term within sup w T r ( w) 2 ; indeed, attempting to plug this construction into Theorem 2.1 does not yield the 1 /δ O(d) rate in Theorem 1.5, but instead a rate 1 /δ O(d/δ) , which is disastrously larger! Interestingly, a fix is possible for special functions of the form f * G α , namely convolutions with Gaussians of coordinate-wise variance α 2 . These are exactly the types of functions used in Section 4 to approximate continuous functions. The fix is simply to apply a change of variable so that, in a sense, the target function and the initialization distribution have similar units. Lemma 3.3. Let function f , variance α 2 > 0, and r ∈ [0, ∞] be given, and define f α := f * G α and φ := (2πα) -1 , and transport mapping T r (w, b) := (0, . . . , 0, p r ( w)) with

T r (w, b) d+1 = p r ( w) := 2 f α (0) + | fα (v)| cos(2π(θ fα (v) -v )) dv + 2π(2πφ 2 ) (d+1)/2 | f (φw)|e b 2 /2 sin(2π(θ fα (φw) -b))1[|b| ≤ w ≤ r]. Then f α (x) = E w T ∞ ( w), Φ(x; w) for x ≤ 1, and for r ∈ [ √ d, ∞), sup w T r ( w) ≤ 2 M + (2πφ 2 ) d/2 M f 1 + 2π 3 φ 2 e r 2 /2 ,

where M := sup x |f (x)|, and M f = 1 when f α = G α and M f = f (φ•) L1 otherwise, and

sup x ≤1 f (x) -E T r ( w), Φ(x; w) ≤ 4π(2πφ 2 ) (d+1)/2 M f ( √ d + 3) exp -(r - √ d) 2 /4 .

4. APPROXIMATING CONTINUOUS FUNCTIONS:

The final piece needed to prove Theorem 1.5 is to show that a function f is close to its Gaussian convolution f * G α , at least when α > 0 is chosen appropriately. This is a classical topic (Wendland, 2004) , and indeed it was used in the original proof of the Weierstrass approximation theorem (Weierstrass, 1885) . The treatment here will include enough detail necessary to yield explicit rates.

The following definition will be used to replace the usual ( , δ) conditions associated with continuous functions with an exact quantity. Definition 4.1. Let f : R d → R be given, and define modulus of continuity ω f as

ω f (δ) := sup f (x) -f (x ) : max{ x , x } ≤ 1 + δ, x -x ≤ δ . ♦

If f is continuous, then ω f (defined here over a compact set) is not only finite for all inputs, but moreover lim δ→0 ω f (δ) → 0. It is also possible to use this definition with discontinuous functions; note additionally that the convolution bounds in Section 3 only required an L 1 bound on the preconvolution function f , and therefore the tools throughout may be applied to discontinuous functions, albeit with some care to their Fourier transforms! Lemma 4.2. Let f : R d → R and δ > 0 be given, and define

M := sup x ≤1+δ |f (x)|, f |δ (x) := f (x)1[ x ≤ 1 + δ], α := δ √ d + 2 ln(2M/ω f (δ)) .

Let G α denote a Gaussian with the preceding variance α 2 . Then

sup x ≤1 f -f |δ * G α ≤ 2ω f (δ).

The proof splits the integrand into two parts: points close to x, and points far from it. Points close to x must behave like f (x) due to continuity, whereas points far from x are rare and do not matter due to the Gaussian convolution. The full details are in the appendix.

Lemma 4.2 can be combined with the transport for f * G α from Section 3 to give a transport for approximating continuous functions.

Theorem 4.3. As in Lemma 4.2, let f : R d → R and δ > 0 be given, and define

M := sup x ≤1+δ |f (x)|, f |δ (x) := f (x)1[ x ≤ 1 + δ], α := δ √ d + 2 ln(2M/ω f (δ)) = O( δ / √ d), r := √ d + 2 ln 4πM f ( √ d + 3) (2πα 2 ) (d+1)/2 ω f (δ)

.

Let G α denote a Gaussian with the preceding variance α 2 , and let T r denote the truncated Fourier map constructed in Lemma 3.3 for f |δ * G α , with preceding truncation choice r. Then

sup w T r ( w) = O   f |δ 5 L1 √ d δ 5(d+1) √ d ω f (δ) 4   , sup x ≤1 f -E w T r ( w), Φ(x; w) ≤ ω f (δ).

This completes all the pieces needed to prove Theorem 1.5.

Proof of Theorem 1.5. Let f be given, and let T r denote the transport mapping provided by Theorem 4.3 for f |δ * G α , whose various parameters match those in the statement of Theorem 1.5. The proof is completed by plugging T r into Theorem 2.1, and simplifying by noting that ≥ ω f (δ) by definition, and

f |δ L1 = O(M ) since δ ≤ 1.

As mentioned earlier, the infinite width network constructed in Lemma 3.1 via inverse Fourier transforms can be used to succinctly prove (via Lemma 2.5 and Lemma 4.2) that threshold and ReLU networks are universal approximators, with a rate vastly improving upon that of Theorem 1.5. Before stating the result, one more tool is needed: a sampling semantics for signed densities; see also (Bach, 2017a; b) for further development and references. Definition 4.4. A sample from a signed (Lebesgue) density p : R d+1 → R with p L1 < ∞ is a pair ( w, s) where w is sampled from the probability density |p| / p L 1 , and s := sgn(p( w)). Let Ep denote the corresponding expectation over ( w, s) ∼ p. ♦

This notion of signed sampling also has a corresponding Maurey lemma, and an analogue for the uniform norm; both are provided in Appendix B. The full detailed universal approximation theorems for threshold and ReLU networks are provided in Appendix E; a simplified form for threshold networks alone is as follows. In either case, the proof proceeds by applying signed density sampling bounds (e.g., appropriate generalizations of Lemma 2.5) to the infinite width networks constructed in Lemma 3.1. Curiously, the simplified bound stated here for threshold networks for the uniform norm is only a multiplicative factor √ d larger than the L 2 (P ) bound in Theorem E.1. Theorem 4.5 (Simplification of Theorem E.1). Let f : R d → R and δ > 0 be given, and define

M := sup x ≤1+δ |f (x)|, f |δ (x) := f (x)1[ x ≤ 1 + δ], α := δ √ d + 2 ln(2M/ω f (δ)) .

Then there exist c ∈ R and p : R d+1 → R with

|c| ≤ M + f |δ L1 (2πα 2 ) d/2 , and p L1 ≤ 2 f |δ L1 2πd (2πα 2 ) d+1 ,

so that, with probability ≥ 1 -3η over ((s j , wj )) m j=1 drawn from p (cf. Definition 4.4),

sup x ≤1 f (x) -   c 1 + p L1 m m j=1 s j σ ( wj , x )   ≤ 2ω f (δ) + p L1 √ m 8 d ln(m) + ln(1/η) .

5. ABSTRACT TRANSPORT MAPPINGS, AND AN RKHS:

Section 3 provided concrete transport mappings via Fourier transforms: it was, for instance, easy to use these constructions to develop approximation rates for continuous functions. These constructions had a major weakness: they were random feature transport mappings, meaning they arguably did not fully utilize the transport sampling provided in Section 2. This section will develop one abstract approach via RKHSes, but first will revisit the random feature constructions.

Suppose f (x) = p( w)σ ( w, x ) d w for some density p; as in the proof of Lemma 3.2, introducing the term

G( w) /G( w) gives f (x) = p( w)

G( w) σ ( w, x ) dG( w), which is now in the desired form, however the ratio term can be large (and a truncation is needed to make it finite in Lemma 3.2). The refined construction in Lemma 3.3 achieved a better bound on sup w T ( w) by being careful about the scaling of the Gaussian, and then standardizing it with a change-of-variable transformation, but still it yields a random feature transport.

Another approach would be to start from the second construction in Lemma 3.1, which writes f (x) = p( w)σ( w, x ) d w = p( w) w, x σ ( w, x ), and thus build a transport around w → p( w) w, which now uses all coordinates. This transport mapping is still just a rescaling, however, and does not lead to improvements when plugged into the other parts of this work.

Consider the following approach to building a general T and an associated Reproducing Kernel Hilbert Space (RKHS). To start, define an inner product •, • H and norm

• H via T 2 H = T , T H = T ( w) 2 2 dG( w) = T 2 L2(G)

; to justify this Hilbert space, note that it gives rise to the usual kernel product (Cho & Saul, 2009) , namely

(x, x ) → E wΦ(x; w) T Φ(x ; w) = Φ(x; •), Φ(x ; •) H ,

and moreover our earlier predictors can be written as E w T ( w), Φ(x; w) = T , Φ(x; •) H .

The utility of these definitions is highlighted in the following bounds; specifically, while a given T may have sup w T ( w) 2 = ∞, truncation can make this quantity finite (and thus Theorem 2.1 may be applied), and the approximation error can be bounded with T H . Proposition 5.1.

1. The output-truncated transport T B ( w) := T ( w)1 T ( w) 2 ≤ B has approximation error

sup x ≤1 T B , Φ(x; •) H -T , Φ(x; •) H ≤ T 2 H √ 2 B 2 . 2. The input-truncated transport T r ( w) := T ( w)1[ w ≤ r] with r > √ d has approximation error sup x ≤1 T r , Φ(x; •) H -T , Φ(x; •) H ≤ T H √ 2 e (r- √ d) 2 /4

.

Unfortunately, this formalism can not be applied to the pre-truncation mapping T ∞ from Lemma 3.3, since T ∞ H = ∞. Consequently, this approach is left as an interesting direction for future work.

6. OPEN PROBLEMS:

The main open question is: how much can the rates 1 /δ 2d for ReLU networks and 1 /δ 10d for their NTK be tightened, and is there a genuine gap? Expanding this inquiry, firstly there are three relevant choices regarding which layers are trained: training just the output layer as with random features (Bach, 2017b; a) , training just the input layer (as in this work), and training both layers. Secondly, for each of these choices, there is a question of norm; e.g., by requiring the maximum over node weight Euclidean norms to be small, the NTK regime is enforced. Are there genuine separations between these settings? Which settings are most relevant empirically? What happens beyond the NTK (Allen-Zhu & Li, 2019)?

Another direction is to use the Fourier tools of Section 2, as well as other tools for constructing transportation maps, and identify function classes with good approximation rates by the NTK and by shallow networks, in particular rates with a merely polynomial dependence on dimension.

Connecting back to the optimization literature, the referenced NTK optimization works for the squared loss seem to require a width which scales with n, and the test error sometimes scales with detailed functions of the observed labels, which require a further argument to go to 0 (see, e.g., y T (H ∞ ) -1 y in (Arora et al., 2019) ). Perhaps such quantities can be replaced with a function space or other approximation theoretic perspective on the conditional mean function (and samples thereof)?

Lastly, what are connections to optimal transport? It seems natural to choose T as an optimal transport, in which case one would hope the parameter B := sup w T ( w) 2 can be small, and moreover easily bounded by the optimal transport cost, ideally in ways similarly easy to the bounding by the Hilbert norm in Proposition 5.1.

A TECHNICAL LEMMAS:

Gaussian Concentration. The following lemma collects a few properties of Gaussian concentration needed throughout.

Lemma A.1. Let w ∼ G d be a standard Gaussian in R d , and let r ≥ √ d be given.

1.:

w dG(w) ≤ √ d.

2.. P[ w > r]:

≤ exp(-(r -√ d) 2 /2); alternatively, with probability at least 1 -η, w ≤ √ d + 2 ln(1/η).

3.:

w >r

w dG(w) ≤ (r + 2) exp -(r - √ d) 2 /2 ≤ 2( √ d + 3) exp -(r - √ d) 2 /4 .

4.:

w >r

w 2 dG(w) ≤ 2(r + 2) 2 exp -(r - √ d) 2 /2 ≤ 2( √ d + 7) 2 exp -(r - √ d) 2 /4 .

The more convenient form of some of the inequalities will need to following technical lemma.

Lemma A.2. Given b ≥ 0 and c > 0 and a ≥ 0 with a + b ≥ 2c and x ≥ b, then

(x + a) exp(-(x -b) 2 /c) ≤ (a + b) exp(-(x -b) 2 /(2c)),

and if moreover a + b ≥ 4c,

(x + a) 2 exp(-(x -b) 2 /c) ≤ (a + b) 2 exp(-(x -b) 2 /(2c)) Proof. Since ln(x + a) ≤ ln(b + a) + (x -b)/(b + a), (x + a) exp(-(x -b) 2 /c) ≤ (a + b) exp(-(x -b) 2 /c + (x -b)/(b + a)) ≤ (a + b) exp(-(x -b) 2 /c + (x -b) 2 /(2c)) ≤ (a + b) exp(-(x -b) 2 /(2c)).

Similarly, multiplying the preceding Taylor expansion by 2,

(x + a) 2 exp(-(x -b) 2 /c) ≤ (a + b) 2 exp(-(x -b) 2 /c + 2(x -b)/(b + a)) ≤ (a + b) 2 exp(-(x -b) 2 /c + 2(x -b) 2 /(4c)) ≤ (a + b) 2 exp(-(x -b) 2 /(2c)). Proof of Lemma A.1. 1. By Jensen's inequality, w dG(w) ≤ w 2 dG(w) = √ d.

2. The claim follows from Gaussian concentration with Lipschitz mappings (Wainwright, 2015, Theorem 2.4), specifically since w → w is 1-Lipschitz, meaning w -w ≤ w -w ,

and since E w < √ d. (r + i + 1) dG(w), whereas the Gaussian concentration from the preceding part grants (r + i + 1) 2 dG(w),

3.. Note that:

P[ w > r + i] ≤ exp(-(r + i - √ d) 2 /2) ≤ exp(-(r - √ d) 2 /2) exp(-i 2 /2),

≤ (r + 1) exp(-(r - √ d) 2 /2) + ∞ i=0 i exp(-(r - √ d) 2 /2) exp(-i 2 /2) ≤ exp(-(r - √ d) 2 /2)   r + 1 + ∞ i=0 i exp(-i 2 /2)   ≤ exp(-(r - √ d) 2 /2) [r + 2] .

≤ 2(r + 1) 2 w >r dG(w) + 2 ∞ i=0 i 2 w >r+i dG(w) ≤ 2(r + 1) 2 exp(-(r - √ d) 2 /2) + 2 ∞ i=0 i 2 exp(-(r - √ d) 2 /2) exp(-i 2 /2) ≤ 2 exp(-(r - √ d) 2 /2)   (r + 1) 2 + ∞ i=0 i 2 exp(-i 2 /2)   ≤ 2 exp(-(r - √ d) 2 /2) [r + 2] 2 .

The final inequality follows by applying Lemma A.2 with (a, b, c, x) = (7,

√ d, 2, r).

Fourier transforms. The convention for the Fourier transform used here is

f (w) = f (x) exp(2πiw T x) dx;

see for instance (Folland, 1999, Section 8.8 ) for a discussion of other conventions, and the resulting tradeoffs. Note also the polar decomposition notation

f (w) = | f (w)| exp(2πiθ f (w)) with |θ f (w)| ≤ 1.

The following lemma collects a few properties used throughout.

Lemma A.3. 1. | f | ≤ f L1 . 2. f * g = f ĝ and | f * g| ≤ f L1 |ĝ|.

3. Let α > 0 be given and define φ := (2πα) -1 . Then | Ĝα | = Ĝα (meaning Ĝα has no radial component, thus θ Gα (w) = 0), and

Ĝα (w) = (2πα 2 ) -d/2 G φ (w) = (2πφ 2 ) d/2 G φ (w) = (2π) d/2 G(w/φ). Proof. 1. Directly, | ĥ(w)| ≤ |h(x)| • | exp(2πiw T x)| dx ≤ h L1 ,

2. The first equality is standard (Folland, 1999, Theorem 8.22c) , and the inequality combines it with the preceding bound.

3. The form of Ĝα and the first displayed inequality are standard (Folland, 1999, Proposition 8.24) . The second and third inequalities use the choice of φ and the form of G φ .

ReLU representation. Lastly, the exact ReLU representation constructions (e.g., Lemma 3.1) will use the following folklore lemma to write a univariate twice continuously differentiable function as an infinite width ReLU network.

Lemma A.4. Let f : R → R be given with f (0) = f (0) = 0 and f continuous. For any z ≥ 0,

f (z) = ∞ 0 σ(z -b)f (b) db.

Proof. Using integration by parts,

∞ 0 σ(z -b)f (b) db = z 0 (z -b)f (b) db = z z 0 f (b) db - z 0 bf (b) db = zf (b)| z 0 -bf (b)| z 0 - z 0 f (b) db = zf (z) -zf (0) -zf (z) -0 -f (z) + f (0) = f (z).

B SAMPLING TOOLS: MAUREY'S LEMMA AND CO-VC DIMENSION:

This section collects various sampling tools used as a basis for Section 2. First is a proof of Lemma 2.5, which here is combined with an application of McDiarmid's inequality to give a high probability guarantee.

Proof of Lemma 2.5. Following the usual Maurey scheme (Pisier, 1980) ,

E (vj ) m j=1 f - 1 m j g j 2 L2(P ) = 1 m 2 E (vj ) m j=1 j f -g j 2 L2(P ) = 1 m 2 E (vj ) m j=1 j f -g j 2 L2(P ) = 1 m E v1 f -g 1 2 L2(P ) = 1 m E v1 g 1 2 L2(P ) -f 2 L2(P ) ≤ 1 m E v1 g 1 2 L2(P ) ≤ 1 m sup v∈V g(•; v) 2 L2(P ) .

The high probability bound will follow from McDiarmid's inequality. To establish the bounded differences property, define

F (V ) := F ((v 1 , . . . , v m )) = f - 1 m j g(•; v j ) L2(P )

, and note from the general metric space inequality p -q ≤ p -q that for any

V = (v 1 , . . . , v m ) and V = (v 1 , . . . , v m ) differing only on a single v k = v k , F (V ) -F (V ) ≤ 1 m j g(•; v j ) - 1 m j g(•; v j ) L2(P ) = 1 m g(•; v k ) -g(•; v k ) L2(P ) ≤ 1 m g(•; v k ) L2(P ) + g(•; v k ) L2(P ) ≤ 2 m sup v∈V g(•; v) L2(P ) .

Thus, with probability at least 1 -η, McDiarmid's inequality grants,

F (V ) ≤ E V F (V ) + sup v∈V g(•; v) L2(P ) 2 ln(1/η) m ,

and the statement follows by Jensen's inequality, specifically

E V F (V ) ≤ E V F (V ) 2 .

Maurey's lemma also applies to sampling from signed densities in the sense of Definition 4.4. Lemma B.1. Let f (x) = p( w)g( w, x ) d w be given with p L1 < ∞ and p is supported on a ball of radius B, and let ((s j , wj )) m j=1 be sampled from p as in Definition 4.4, and define g j (x) := g( w, x ). With probability at least 1 -η,

f - p L1 m m j=1 s j g j L 2 (P ) ≤ sup w ≤B g( w, • ) L2(P ) p L1 1 + 2 ln(1/η) √ m . Proof. Since p( w)g( w, x ) d w = p L1 sgn(p) |p( w)| p L1 g( w, x ) d w = p L1 E s, w sg( w, x ),

the sampling procedure indeed provides an unbiased estimate of the integral, and thus by Maurey's Lemma (cf. Lemma 2.5), with probability at least 1 -η,

f - p L1 m m j=1 s j g j L 2 (P ) = p L1 E s, wsg( w, • ) - 1 m m j=1 s j g j L 2 (P ) ≤ p L1 sup s∈{±1} w ≤B sg( w, • ) L2(P ) 1 + 2 ln(1/η) √ m = p L1 sup w ≤B g( w, • ) L2(P ) 1 + 2 ln(1/η) √ m .

Lastly, here is a uniform norm analog of the preceding L 2 (P ) signed density sampling bound. Interestingly, the bound only gives a √ d degradation with σ , and no degradation for σ. The method of proof is to use uniform convergence, but with data and parameters switched; consequently, this has been called "co-VC dimension" (Gurvits & Koiran, 1995; Sun et al., 2018) . The proof is somewhat more complicated than the proof of the Maurey lemma, and in particular needs to be a bit more attentive to the fine-grained structure of the functions being sampled. Lemma B.2. Let density p : R d+1 → R with p L1 < ∞, and let ((s j , w j )) m j=1 be a sample from p in the sense of Definition 4.4.

1.. With probability at least:

1 -2η, sup x ≤1 p( w)σ ( w, x ) d w - p L1 m j s j σ ( wj , x ) ≤ p L1 √ m 8(d + 1) ln(m + 1) + ln(1/η) .

2. Suppose p is supported on the set

W := { w ∈ R d+1 : w ≤ r, |b| ≤ w }. With probability at least 1 -2η, sup x ≤1 p( w)σ( w, x ) d w - p L1 m j s j σ( wj , x ) ≤ 4r p L1 √ m 1 + ln(1/η) .

Proof of Lemma B.2. In both cases, letting g denote either of σ or σ,

sup x ≤1 p( w)g( w, x ) d w - p L1 m j s j g( wj , x ) = p L1 sup x ≤1 E p sg( w, x ) d w - 1 m j s j g( wj , x ) ,

and at this point it is a classical uniform deviations problem, but with the role of parameter and data swapped, an approach which has been used before (sometimes under the heading "co-VC dimension" (Gurvits & Koiran, 1995; Sun et al., 2018) ). Continuing, with probability at least 1 -2η, standard Rademacher complexity (Shalev-Shwartz & Ben-David, 2014) grants

sup x ≤1 E p sg( w, x ) d w - 1 m j s j g( wj , x ) ≤ 2Rad (s j g( wj , x )) m j=1 : x ≤ 1 + 3 sup w∈W x ≤1 |g( w, x )| ln(1/η) 2m .

where W is a constraint set on w (when g = σ , it is R d+1 , whereas with g = σ it is |b| ≤ w ≤ r).

To simplify further, note that a Rademacher random vector ( 1 , . . . , m ) is distributionally equivalent to (s 1 1 , . . . , s m m ) for any fixed vector of signs (s 1 , . . . , s m ), and therefore

Rad (s j g( wj , x )) m j=1 : x ≤ 1 = 1 n E sup x ≤1 j s j j g( w, x ) = 1 n E sup x ≤1 j j g( w, x ) = Rad (g( wj , x )) m j=1 : x ≤ 1 .

Combining these steps, with probability at least 1 -2η,

sup x ≤1 p( w)g( w, x ) d w - p L1 m j s j g( wj , x ) ≤ p L1   2Rad (g( wj , x )) m j=1 : x ≤ 1 + 3 sup w∈W x ≤1 |g( w, x )| ln(1/η) 2m    .

The proof now splits into two cases g ∈ {σ , σ}, bounding the remaining terms.

1. Since the range of σ is {0, 1}, sup

w∈W x ≤1 |σ ( w, x )| ≤ 1,

and the Rademacher complexity is the VC dimension of linear predictors, thus

Rad (σ ( wj , x )) m j=1 : x ≤ 1 ≤ 2(d + 1) ln(m + 1) m .

2. In the case g = σ, since

W := { w ∈ R d+1 : w ≤ r, |b| ≤ w }, sup w∈W x ≤1 |σ( w, x )| ≤ sup w ≤r |b|≤ w x ≤1 |w T x + b| ≤ 2r.

Moreover, the Rademacher complexity is a standard combination of the Lipschitz composition rule and linear prediction rules (Shalev-Shwartz & Ben-David, 2014) , and thus

Rad (σ ( wj , x )) m j=1 : x ≤ 1 ≤ Rad ( wj , x ) m j=1 : x ≤ 1 ≤ 4r √ m .

C DEFERRED PROOFS FROM SECTION 2

For convenience throughout this appendix, define

B := sup w T ( w) and B := sup w,s T ( w, s) 2 ≤ B √ m + R.

The first step is to prove eq. ( 2.2), restated here as follows.

Lemma C.1. With probability at least 1 -η over ( W , S),

m j=1 τ j , φ j (•) -E w T ( w), Φ(•; w) L 2 (P ) ≤ B √ 2 + 2 ln(1/η) .

Proof. The proof proceeds by applying Maurey sampling (cf. Lemma 2.5) to the functions g j (x) := m τ j , φ j (x) , noting by Lemma 2.4 that

f (x) := E W ,S 1 m j g j (x) = E W ,S j τ j , φ j (x) = E W ,S T ( W , S), Φ (x; W , S) = E w T ( w), Φ(x; w) .

Applying Lemma 2.5, with probability at least 1 -η,

f - 1 m m j=1 g j L 2 (P ) ≤ sup w,s m T ( w, s), Φ (•; w, s) L2(P ) √ m 1 + 2 ln(1/η) ,

where

sup w,s T ( w, s), Φ (•; w, s) 2 L2(P ) ≤ sup w,s E x T ( w) 2 2 Φ (x; w, s) 2 2 ≤ 2 2 B 2 m .

Next, the restatement of eq. ( 2.3) is as follows.

Lemma C.2. With probability at least 1 -η, If R ≥ √ d + 2 ln √ mπ B √ 2 , then with probability at least 1 -η, j τ j , φ j (•) - j s j √ m σ( τ j , x ) L2(P ) ≤ B B m √ π + B √ 2 + 2 ln(1/η) .

Recall that the proof of Lemma C.2, as discussed in the body, must calculate the fraction of activations which change, which was collected into Lemma 2.6.

Proof of Lemma 2.6. Consider an idealized T which does not truncate, whereby

| T ( w), x | -| w, x | ≤ T ( w), x √ m + w, x -w, x ≤ B x √ m .

The event sgn( w, x ) = sgn( T ( w), x ) implies the event | w, x | ≤ B x / √ m , and thus, additionally using rotational invariance of the Gaussian,

E w σ ( w, x ) -σ ( T ( w), x ) = P w sgn( w, x ) = sgn( T ( w), x ) ≤ P w | w, x | ≤ B x / √ m = P w |w 1 | • x ≤ B x / √ m = 1 √ 2π B/( √ m) -B/( √ m) e -z 2 /2 dz ≤ B 2 mπ .

Returning to the general case with truncation, by Lemma A.1, using the assumed lower bound on R,

P[ w > R] ≤ exp(-(R - √ d) 2 /2) ≤ B 2 mπ ,

which gives the final bound via triangle inequality.

With Lemma 2.6 in hand, the proof of Lemma C.2 is now an application of Maurey's lemma, with an invocation of positive homogeneity to massage terms.

Proof of Lemma C.2. The approach is once again to apply Maurey sampling (cf Lemma 2.5). To this end, define

g(x; w, s) := m T ( w, s), Φ (x; w, s) - s √ m σ T ( w, s), x and f (x) = E w,s g(x; w, s),

as well as g j (x) := g(x; wj , s j ). Using this notation, the goal of this proof is to upper bound

j τ j , φ j (•) - j s j √ m σ( τ j , • ) L2(P ) = 1 m j g j L2(P )

.

By Lemma 2.5, with probability at least 1 -η,

1 m j g j L2(P ) ≤ f L2(P ) + f - 1 m j g j L2(P ) ≤ f L2(P ) + sup w,s g(•; w, s) L2(P ) 1 + 2 ln(1/η) √ m .

To control these terms, fixing any ( w, s), it holds by positive homogeneity of σ that g(x; w, s)

2 L2(P ) = m 2 E x T ( w, s), Φ (x; w, s) - s √ m Φ(x; T ( w, s)) 2 ≤ m 2 B 2 E x 2 x 2 m ≤ 2m 2 B 2 .

On the other hand, by Lemma 2.6, for any x ≤ 1,

|f (x)| ≤ E w,s T ( w, s), Φ (x; w, s) - s √ m Φ(x; T ( w, s)) ≤ B E w,s x σ (T ( w) T x) -σ ( wT x) √ m ≤ B √ m B √ mπ ,

which also upper bounds f L2(P ) . 

D DEFERRED PROOFS FROM SECTION 3:

The first core lemma shows how to write a target function f as an infinite-width network via its Fourier transform.

Proof of Lemma 3.1. The first steps are the same for σ and σ , and indeed match the initial steps of (Barron, 1993) , namely

f (x) -f (0) = Re exp(2πix T w) f (w) dw = Re exp(2πix T w + 2πiθ f (w))| f (w)| dw = cos 2π(x T w + θ f (w)) | f (w)| dw.

For convenience, define h(z) := cos(2πz), whereby

f (x) -f (0) = h(x T w + θ f (w))| f (w)| dw, (D.1)

and the proofs not differ for both activations and from (Barron, 1993) .

1. Consider first σ . Since x ≤ 1, by Cauchy-Schwarz it suffices to approximate h along the interval [-w + θ f (w), w + θ f (w)]. By the fundamental theorem of calculus,

h( w, x + θ f (w)) -h -w + θ f (w) = w,x +θ f (w) -w +θ f (w) h (b) db = h (b)1[ w, x + θ f (w) ≥ b]1[b ≥ -w + θ f (w)] db = -h (θ f (w) -b)1[x T w + b ≥ 0]1[ w ≥ b] db, b → θ f (w) -b = -h (θ f (w) -b)1[x T w + b ≥ 0]1[ w ≥ |b|] db,

where the last step follows since 1[x T w + b ≥ 0] implies b ≥ -w . Plugging this back in to eq. (D.1) and still using h(z) = cos(2πz),

f (x) -f (0) = | f (w)| cos 2π(x T w + θ f (w)) dw = | f (w)| h(-w + θ f (w)) -h (θ f (w) -b)1[x T w + b ≥ 0]1[ w ≥ |b|] db dw,

which after pushing more terms onto the left hand side gives

f (x) -f (0) -| f (w)|h(θ f (w) -w ) dw = - | f (w)|h (θ f (w) -b)1[x T w + b ≥ 0]1[ w ≥ |b|] db dw = 2π | f (w)| sin(2π(θ f (w) -b))σ ( w, x )1[ w ≥ |b|] d w,

which gives F ∞ = f for x ≤ 1. To bound the error of F r , note by the form of F ∞ for any x ≤ 1 that

f (x) -F r (x) = 2π w >r | f (w)| sin(2π(θ f (w) -b))σ ( w, x )1[ w ≥ |b|] db dw ≤ 2π w >r |b|≤ w | f (w)|| sin(2π(θ f (w) -b))|σ ( w, x ) db dw ≤ 2π w >r | f (w)| |b|≤ w db dw = 4π w >r w • | f (w)| dw.

2. Now consider σ. Rather than using FTC as above, this proof replaces h with ReLUs via Lemma A.4, which requires a function which is both zero and flat at 0. To this end, define

H(b) = h(b + q) -h(q) + bh (q) with q = -w + θ f (w),

whereby H(0) = 0 = H (0). Invoking Lemma A.4 on H gives, for any z :

= w T x + θ f (w) ≥ q, h(z) -h(q) + (z -q)h (q) = H(z -q) = H (b)σ(z -q -b)1[b ≥ 0] db = H (b)σ(w T x + θ f (w) + w -θ f (w) -b)1[b ≥ 0] db = -H ( w -b)σ(w T x + b)1[ w ≥ b] db b → w -b = -H ( w -b)σ(w T x + b)1[ w ≥ |b|] db,

the final equality since -b > w implies w T x + b ≤ w + b < 0, thus σ( wT x) = 0 and this case has no effect. Plugging this back into eq. (D.1),

f (x) -f (0) = | f (w)|h(z) dw = | f (w)| h(q) + (z -q)h (q) -H ( w -b)σ( wT x)1[ w ≥ |b|] db dw = | f (w)| h(q) + (w T x + w )h (q) -H ( w -b)σ( wT x)1[ w ≥ |b|] db dw,

which gives Q ∞ = f for x ≤ 1 after expanding h and H. To bound the error of Q r , for any x ≤ 1

f (x) -Q r (x) = w >r | f (w)| H ( w -b)σ( wT x)1[ w ≥ |b|] db dw ≤ w >r | f (w)| |H ( w -b)|σ( wT x)1[ w ≥ |b|] db dw ≤ 4π 2 w >r | f (w)| w -w σ( wT x) db dw ≤ 4π 2 w >r | f (w)| w -w ( w + |b|) db dw ≤ 12π 2 w >r w 2 • | f (w)| dw.

Next, Lemma 3.2 converts Lemma 3.1 into a (random feature) transport map by introducing the fraction G( w) /G( w).

Proof of Lemma 3.2. Starting from the construction in Lemma 3.1, again using h(z) = cos(2πz) for convenience, and manually introducing a factor G( w),

f (x) -f (0) -| f (w)|h(θ f (w) -w ) dw = - | f (w)|h (θ f (w) -b)1[x T w + b ≥ 0]1[ w ≥ |b|] db dw = - | f (w)| G( w) h (θ f (w) -b)σ ( w, x )1[ w ≥ |b|] dG( w).

To construct T ∞ , rotational invariance of the Gaussian gives E1[ wT x ≥ 0] = 1 /2, thus

f (0)+ | f (w)|h(θ f (w)-w ) dw = 2 f (0) + | f (v)|h(θ f (v) -v ) dv σ ( w, x ) dG( w),

and transport mapping is

T ∞ (w, b) = (0, p ∞ ( w)) ∈ R d × R with p ∞ ( w) = 2 f (0) + | f (v)|h(θ f (v) -v ) dv - | f (w)| G( w) h (θ f (w) -b)1[ w ≥ |b|],

By construction, E w T r ( w), Φ(x; w) = F r (x), and therefore Lemma 3.1 grants for all x ≤ 1

f (x) = E w T ∞ ( w), Φ(x; w) and f (x) -E T r ( w), Φ(x; w) ≤ 4π w >r | f (w)|• w dw.

With more care (in particular, a crucial change of variable), a much better bound is possible for convolutions with Gaussians.

Proof of Lemma 3.3. By Lemma A.3, setting φ :=

(2πσ) -1 , | fα (w)| = | f (w)| Ĝα (w) = (2π) d/2 | f (w)|G(w/φ).

Plugging this into Lemma 3.1 and again defining h(z) := cos(2πz) for convenience, but unlike Lemma 3.2 performing a change of variable to directly introduce G( w), and then manually introducing

G(b), f α (x) -f α (0) -| fα (w)|h(θ fα (w) -w ) dw = - | fα (w)|h (θ fα (w) -b)σ ( wT x)1[ w ≥ |b|] db dw = -(2π) d/2 | f (w)|G(w/φ)h (θ fα (w) -b)σ ( wT x)1[ w ≥ |b|] db dw = -(2πφ 2 ) d/2 φ | f (φw)|G(w)h (θ fα (φw) -b)σ (φ w, x )1[φ w ≥ φ|b|] db dw = -(2πφ 2 ) (d+1)/2 | f (φw)|e b 2 /2 h (θ fα (φw) -b)σ ( w, x )1[ w ≥ |b|] dG( w).

As in Lemma 3.2, the transport is constructed by using Eσ ( w, x ) = 1 /2 to model constants: T r (w, b) = (0, . . . , 0, p r ( w)), where 

p r ( w) := 2 f α (0) + | fα (v)|h(θ fα (v) -v ) dv -(2πφ 2 ) (d+1)/2 | f (φw)|e b 2 /2 h (θ fα (φw) -b)1 |b| ≤ w ≤ r , with f (x) = E w T ∞ ( w), Φ(x; w) for x ≤ 1 by construction. When r < ∞, by construction sup w T r ( w) ≤ 2 f α (0) + 2 | fα (v)| dv + 2π(2πφ 2 ) (d+1)/2 sup w ≤r |b|≤ w | f (φw)|e b 2 /2 , where | f (φw)| = 1 when f α = G α (meaning f itself

sup w T r ( w) ≤ 2 f (x)G α (-x) dx + 2(2π) d/2 | f (v)|G(v/φ) dv + 2π(2πφ 2 ) (d+1)/2 M f sup |b|≤r e b 2 /2 ≤ 2 M + 2(2πφ 2 ) d/2 M f + 2π(2πφ 2 ) (d+1)/2 M f sup |b|≤r e b 2 /2 .

For the approximation estimate, for any x ≤ 1, the preceding derivation and Lemma A.1 grant

f (x) -E T r ( w), Φ(x; w) = E T ∞ ( w) -T r ( w), Φ(x; w) ≤ 2π(2πφ 2 ) (d+1)/2 w >r |b|≤ w | f (φw)|| sin(2π(w T x + θ fα (w)))σ ( wT x)| db dG(w) ≤ 2π(2πφ 2 ) (d+1)/2 M f w >r |b|≤ w db dG(w) ≤ 4π(2πφ 2 ) (d+1)/2 M f w >r w dG(w) ≤ 4π(2πφ 2 ) (d+1)/2 M f ( √ d + 3) exp -(r - √ d) 2 /4 .

E DEFERRED PROOFS FROM SECTION 4:

The first proof is of the approximation properties of Gaussian convolution; as stated in the body, the proof proceeds by splitting the error into two terms, one for nearby points, the other for distant points.

Proof of Lemma 4.2. Splitting the integral into two terms, for any x ≤ 1,

f (x) -(f |δ * G α )(x) = f |δ (x)G α (z) dz -f |δ (z)G α (x -z) dz = f |δ (x)G α (z) dz -f |δ (x -z)G α (z) dz ≤ f |δ (x) -f |δ (x -z) G α (z) dz = z ≤δ f |δ (x) -f |δ (x -z) G α (z) dz + z >δ f |δ (x) -f |δ (x -z) G α (z) dz.

Analyzing these terms separately, the definition of ω f (δ) gives

z ≤δ f |δ (x) -f |δ (x -z) G α (z) dz ≤ z ≤δ ω f (δ)G α (z) dz ≤ ω f (δ),

whereas Gaussian concentration (cf. Lemma A.1) gives z >δ

f |δ (x) -f |δ (x -z) G α (z) dz ≤ 2M P[ αz > δ] ≤ 2M exp(-(δ/α- √ d) 2 /2) ≤ ω f (δ).

This now combines with Lemma 3.3 to prove Theorem 4.3.

Proof of Theorem 4.3. Plugging the choice of r into Lemma 3.3, for any x ≤ 1,

f (x) -E T r ( w), Φ(x; w) ≤ 4π(2πφ 2 ) (d+1)/2 M f ( √ d + 3) exp -(r - √ d) 2 /4 ≤ ω f (δ).

Moreover, plugging r into the estimate on sup w T r ( w) provided by Lemma 3.3 gives , where e (r-

sup w T r ( w) ≤ 2 M + (2πφ 2 ) d/2 M f 1 + 2π 3 φ 2 e r 2 /

√ d) 2 = 4π(2πφ 2 ) (d+1)/2 M f ( √ d + 3) ω f (δ) 4 = O   M f √ d ω f (δ)α d+1 4   ,

and noting moreover that α = O(δ/ √ d).

To close this section comes the full version of Theorem 4.5, which gives explicit constructions for both threshold σ and ReLU σ. Interestingly, in the case of σ , it is not necessary to truncate the density, as is the case everywhere else in this work. Theorem E.1. As in Lemma 4.2, let f : R d → R and δ > 0 be given, and define

M := sup x ≤1+δ |f (x)|, f |δ (x) := f (x)1[ x ≤ 1 + δ], α := δ √ d + 2 ln(2M/ω f (δ)) .

Let G α denote a Gaussian with the preceding variance α 2 , and define h := f |δ * G α with Fourier transform ĥ satisfying radial decomposition ĥ(w) = | ĥ(w)| exp(2πiθ h (w). Lastly, let P be a probability measure supported on x ≤ 1. .

:

√m).

Figures and Tables:

Let f : R d → R be given with Fourier transform f and truncation radius r ∈ [0, ∞].

The final inequality follows by applying Lemma A.2 with (a, b, c, x) = (3, √ d, 2, r)

is the Dirac at 0), and more generally Lemma A.3 grants | f (φw)| ≤ f (φ•) L1 ; as in the lemma statement, these cases are summarized with | f (φw)| ≤ M f . Plugging this in and simplifying further via Lemma A.3,

:= h(0)+ | ĥ(w)| cos 2π(θ h (w) -w ) dw, p 1 := 2π| ĥ(w)| sin(2π(θ h (w)-b))1 |b| ≤ w .Then|c 1 | ≤ M + f |δ L1 (2πα 2 ) d/2 ,andp 1 L1 ≤ 2 f |δ L1 2πd (2πα 2 ) d+1 ,and with probability at least 1 -3η over a draw of ((s j , wj )) m j=1 from p 1 (cf. Definition 4.4), + 1) ln(m + 1) + ln(1/η) .2. Additionally definec 2 := f (0)f (0) + | ĥ(w)| cos(2π(θ h (w) -w )) -2π w sin(2π(θ h (w) -w )) dw, a 2 := w| ĥ(w)| dw, 2 f |δ L1 ω f (δ) , p 2 ( w) := 4π 2 | ĥ(w)| cos(2π( w -b))1[|b| ≤ w ≤ r 2 ],and for convenience create fake (weight, bias, sign) triples (w, b, s) m+1 := (0, |c 2 |, m • sgn(c 2 )), (w, b, s) m+2 := (a 2 , 0, +m), (w, b, s) m+3 := (-a 2 , 0, -m).Thena 2 2 ≤ √ d f |δ L1 φ(2πα 2 ) -d/2 , p 2 L1 ≤ 2 f |δ L1 (2π) 3 d (2πα 2 ) d+1 , |c 2 | ≤ M + 2 √ d f |δ L1 (2πα 2 ) -d/2 ,and with probability at least 1 -3η over a draw of ((s j , wj )) m j=1 from p 2 (cf. Definition 4.4), Lemma 3.1 and the choice of b 1 , for any x ≤ 1,h(x) = c 1 + p 1 ( w)σ ( w, x ) d w,thus by Lemma 4.2 and Lemma B.1, defining h j := p L1 σ ( wj , • ) for convenience, with probability at least 1uniform norm bound follows by Lemma 4.2 and Lemma B.2: with probability at least 1 -2η, for any x ≤ 1,f (x) -(c 1 + j h j (x)/m) ≤ f (x) -h(x) + h(x) -(c 1 + j h j (x)/m) ≤ 2ω f (δ) + p 1 L1 √ m 8(d + 1) ln(m + 1) + ln(1/η) .For the estimates on |c 1 | and p 1 L1 , note setting φ := (2πα) -1 , note by Lemma A.3 and a change of variable w → φw and Lemma A.1 thatp 1 L1 ≤ 2π | f |δ * G α (w)| 1[|b| ≤ w ] db dw ≤ 4π f |δ L1 w (2πφ 2 ) d/2 G φ (w) dw = 4π(2π) d/2 f |δ L1 φw φ d G(w) dw ≤ 4π(2π) d/2 φ d+1 f |δ L1 w G(w) dw ≤ 4 √ dπ(2π) d/2 φ d+1 f |δ L1 , ≤ 2 f |δ L1 2πd (2πα 2 ) d+1 .Similarly,|c 1 | ≤ M + f |δ L1 Ĝα (w) dw ≤ M + f |δ L1 (2πφ 2 ) d/2 .2. By Lemma 3.1 and Lemma A.1 and the various chosen parameters, for any x ≤ 1,b 2 + x, a 2 + p 2 ( w)σ( w, x ) d w -h(x)Thus by Lemma 4.2 and Lemma B.1, defining h j := p L1 s j σ( wj , • ) for convenience, with probability at least 1hL2(P ) + f -(b 2 + (•) T c 2 + E p2 s 1 h 1 + E p2 s 1 h 1 -m j=1 s j h j /m L2(P ) ≤ 3ω f (δ) + p 2 L1 sup w ≤r2 σ( w, • L2(P ) 1 + 2 ln(1/η) √ m ≤ 3ω f (δ) + 2r 2 p L1 1 + ln(1/η) √ m .Similarly, the uniform norm bound follows by Lemma 4.2 and Lemma B.2: with probability at least 1 -2η, for any x ≤ 1,f (x) -m+3 j=1 h j (x)/m ≤ f (x) -h(x) + f (x) -(b 2 + x T c 2 + E p2 s 1 h 1 (x) + E p2 s 1 h 1 (x) -For the estimates on |c 1 | and p 1 L1 , note setting φ := (2πα) -1 , note by Lemma A.3 and a change of variable w → φw and Lemma A.1 thatp 2 L1 ≤ 4π 2 | f |δ * G α (w)| 1[|b| ≤ w ≤ r 2 ] db dw ≤ 8π 2 f |δ L1 w ≤r2 w (2πφ 2 ) d/2 G φ (w) dw = 8π 2 (2π) d/2 f |δ L1 φw ≤r2 φw φ d G(w) dw ≤ 8π 2 (2π) d/2 φ d+1 f |δ L1 φw ≤r2 w G(w) dw ≤ dπ 2 (2π) d/2 φ d+1 f |δ L1 ≤ 2 f |δ L1 (2π) 3 d (2πα 2 ) d+1 .Similarly,|c 2 | ≤ M + f |δ L1 (1 + w ) Ĝα (w) dw ≤ M + f |δ L1 (2πφ 2 ) d/2 (1 + φw ) dG(w) ≤ M + 2 √ d f |δ L1 (2πφ 2 ) d/2 , a 2 2 = w| ĥ(w)| dw ≤ w | ĥ(w)| dw ≤ f |δ L1 (2πφ 2 ) d/2 φw | ĥ(w)| dw ≤ √ d f |δ L1 φ(2πφ 2 ) d/2 .F DEFERRED PROOFS FROM SECTION 5Lastly, the two short proofs leading to the RKHS bounds.Proof of Proposition 5.1. 1. By Markov's inequality1[ T ( w) 2 > B] dG( w) ≤ T 2 H B 2 ,thus by Cauchy-Schwarz, for any x ≤ 1, T B , Φ(x; •) H -T , Φ(x; •) H = T B ( w) -T ( w) T xσ ( w, x ) dG( w) ≤ 1 T ( w) 2 > B • T ( w) T x • σ ( w, x ) dG( w) similarly, but now using Lemma A.1 to control the indicator, T r , Φ(x; •) H -T , Φ(x; •) H = T r ( w) -T ( w) T xσ ( w, x ) dG( w) ≤ 1 w 2 > r • T ( w) T x • σ ( w, x ) dG( w)

The proof of Theorem 2.1 now follows by combining Lemmas C.1 and C.2.Proof of Theorem 2.1. By Lemma A.1 and a union bound on ( w1 , . . . , wm ), max j wj ≤ R, thus

Table content: <table><tr><td/><td/><td>max j</td><td>T ( wj ) -wj ≤ max j</td><td>T ( wj ) √ m</td><td>≤</td><td>B √ m</td><td>.</td></tr><tr><td>Moreover, R ≥</td><td>√</td><td>d + 2 ln</td><td colspan="4">√ B √ mπ 2 , and thus the two other bounds are from Lemmas C.1 and C.2.</td></tr></table>

Peer review (iclr2020):
Summary: the paper consider representational aspects of neural tangent kernels (NTKs). More precisely, recent literature on overparametrized neural networks has identified NTKs as a way to characterize the behavior of gradient descent on wide neural networks as fitting these types of kernels. This paper focuses on the representational aspect: namely that functions of appropriate *complexity* can be written as an NTK with parameters close to initialization (comparably close to what results on gradient descent get). The main technical ingredients are a constructing a *transport* map via a Fourier-expansion style averaging (ala Baron), and subsequently subsampling this average ala Maurey-style analyses to get a finite width average. The authors also identify function classes which are well-behaved with respect to these techniques: smoothed functions (via convolving with a Gaussian), functions which have a small RKHS norm (for an appropriate RKHS derived from NTKs), functions with small modulus of continuity. Evaluation: the paper is a strong contribution, on a topic which is of great current interest, and I recommend acceptance. It is very nice that many of the standard tools in approximation theory (Fourier expansions, Maurey sampling, etc.) play nicely with NTKs, and also that the scaling of the # of neurons necessary that appears in the current literature can be also recovered via a representation theoretic viewpoint. The paper is written well, and is easy to read. Minor comments: * I*d rearrange the bullets bounding B_{f,epsilon} for the various subcases of Theorem 1.3: I think the RKHS is the most *vanilla* bound, given that you can extract a RKHS; bounds in terms of the modulus of continuity should go next (this is the *weakest* assumption); smoothed f*s should go last (this is like a smoothed complexity kind of result) * w_f isn*t defined until section 3.2 -- I*d put a pointer in the statement of Theorem 1.3 to the equation, not just the section. * I*m not sure *transport* is the ideal term -- it brings to mind *optimal transport*, and I kept expecting some Wasserstein connection.