Year: 2020

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/δ 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/δ 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

heading: 1 MAIN RESULT AND OVERVIEW
text: Consider functions computed by a single ReLU layer, meaning
x 7→ m∑ j=1 sjσ (〈 wj , x 〉 + bj ) , (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 7→ √ m m∑ j=1 sj 〈 τj , x̃ 〉 σ′ (〈 w̃j , x̃ 〉) , where x̃ = (x, 1) ∈ Rd+1, w̃ = (w, b) ∈ Rd+1; (1.2)
here each w̃j = (wj , bj) 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 w̃j , concretely ‖τj − w̃j‖ = 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 ofm, specifically ‖τj − w̃j‖2 = O(1/ √m).
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 − w̃j‖ = 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 − w̃j‖ = 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 − w̃j‖ = 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.

heading: 1.1 BASIC NOTATION, INTUITION, AND MAIN RESULT
text: 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 : Rd+1 → Rd+1 to show where weights should go: x 7→ Ew̃ 〈 T (w̃),Φ(x; w̃) 〉 = Ew̃ 〈 T (w̃), x̃ 〉 σ′(〈w̃, x̃〉) = Ew̃ 〈 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)mj=1 from before into transported weights defined over arbitrary weights w̃ ∈ Rd+1. These (augmented) weights w̃ = (w, b) (with weight w ∈ Rd 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 〈 s2T (w̃) + sw̃ √ m,Φ(x; w̃) 〉 ∵ E s2 = 1,E s = 0
≈ 1
m m∑ j=1 〈 s2jT (w̃j) + sjw̃j √ m,Φ(x; w̃j) 〉 sampling (wj , sj)
= √ m m∑ j=1 〈 sjT (w̃j) √ m + w̃j , sjΦ(x; w̃j) 〉 .
(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 (w̃j , sj) := sjT (w̃j) √ m + w̃j1[‖w̃j‖ ≤ R],
φj(x) := Φ (x; w̃j , sj) := sj√ m Φ(x; w̃j) = sj√ m x̃σ′(
〈 w̃j , x̃ 〉 ),
(1.4)
where R is a truncation radius included for purely technical reasons. The transport mappings constructed in Section 3 satisfy B := supw̃ ‖T (w̃)‖ < ∞, and thus maxj ‖τj − w̃j‖ ≤ 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 L2(P ) metric, where P is a probability measure on the ball {x ∈ Rd : ‖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 L2
and L1 metrics over functions on Rd. Theorem 1.5 (Simplification of Theorems 2.1 and 4.3). Let continuous function f : Rd → 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̃
( M5d(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 (w̃j)mj=1 and uniform signs (sj)mj=1, then maxj ‖τj − w̃j‖ ≤ B/ √m, and∥∥∥∥∥∥f − m∑ j=1 〈 τj , φj(·) 〉∥∥∥∥∥∥ L2(P ) ≤ Õ ([ B√ m + √ d ]√ ln(1/η) ) ,
∥∥∥∥∥∥ √m m∑ j=1 sjσ( 〈 τj , x̃ 〉 )− m∑ j=1 〈 τj , φj(·) 〉∥∥∥∥∥∥ L2(P ) ≤ Õ [ B2 m3/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̃(d5d+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̃(dd+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?

heading: 1.2 RELATED WORK
text: 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 σ′( 〈 w̃j , x̃ 〉 ) are held fixed, and what are trained are scalar weights aj ∈ 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 (w̃j)mj=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 : Rd → 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 L2(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.

heading: 2 SAMPLING FROM A TRANSPORT
text: This section establishes that by sampling from an infinite width NTK, the resulting finite width NTK is close in L2(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, supw̃ ‖T (w̃)‖2 } , and set R := √ d+ 1 + 2 √ ln(m/η). With probability at least 1− 3η, then maxj ‖τj − w̃j‖ ≤ B/ √m, and∥∥∥∥∥∥ m∑ j=1 〈 τj , φj(·) 〉 − Ew̃ 〈 T (w̃),Φ(·; w̃) 〉∥∥∥∥∥∥ L2(P ) ≤ 2 ( B√ m + R )[ 1 + √ ln(1/η) ] , (2.2)
∥∥∥∥∥∥ ∑ j 〈 τj , φj(·) 〉 − ∑ j sj √ m σ( 〈 τj , · 〉 ) ∥∥∥∥∥∥ L2(P ) ≤ 2 ( B2 m3/2 + BR m + B√ m + R )[ 1 + √ ln(1/η) ] .
(2.3)
As discussed in the introduction, maxj ‖τj − w̃j‖ ≤ 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, meaningW = (w̃1, . . . , w̃m) and S = (s1, . . . , sm). Lemma 2.4. Ẽ
w
〈 T (w̃),Φ(x; w̃) 〉 = E W̃ ,S ∑ j 〈 T (w̃j , sj),Φ (x; w̃j , sj) 〉 = 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 := supw̃ ‖T (w̃)‖2. Lemma 2.5 (Maurey). Let functions {g(·; v) : v ∈ V} be given, where V ⊆ Rp is a set of possible parameters. Let ν be a probability measure over V , let (v1, . . . , vm) be an iid random draw from ν, and define
f(x) := E v∼ν g(x; v) and gj(x) := g(x; vj).
Then
E ((sj ,vj))mj=1 ∥∥∥∥∥∥f − 1m m∑ j=1 gj ∥∥∥∥∥∥ 2
L2(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 − 1m m∑ j=1 gj ∥∥∥∥∥∥ L2(P ) ≤ sup v∈V ‖g(·; v)‖L2(P ) [ 1 + √ 2 ln(1/η)√ m ] .
Concretely, here gj(x) = m 〈 τj , φj(x) 〉 , and supv∈V ‖g(·; w̃)‖L2(P ) ≤ √ 2 supw̃ ‖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 sjσ( 〈 τj , x̃ 〉 ) = m∑ j=1 〈 τj , φj − sj √ m x̃σ′( 〈 τj , x̃ 〉 ) 〉 ,
which boils down to checking the difference in activations, namely σ′( 〈 w̃j , x̃ 〉 )− σ′( 〈 τj , x̃ 〉 ). As
is standard in the NTK literature, since τj − w̃j is (with high probability) microscopic compared to〈 w̃j , x̃ 〉 , the activations should also be close. The following lemma makes this precise. Lemma 2.6. For any x ∈ Rp, 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 maxj ‖w̃j‖ ≤ R. This also establishes the first half of Theorem 1.5.

heading: 3 CONCRETE TRANSPORT MAPPINGS VIA FOURIER TRANSFORMS
text: 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πixTw ) 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 Ew̃ 〈 T (w̃),Φ(x; w̃) 〉 = Ew̃p(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 7→ exp(2πixTw):
f(x) = ∫ exp(2πixTw)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πixTw)f̂(w) dw
= Re ∫ exp(2πixTw + 2πiθf (w))|f̂(w)|dw
= ∫ cos ( 2π(xTw + θ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.
Lemma 3.1. Let f : Rd → R be given with Fourier transform f̂ and truncation radius r ∈ [0,∞].
1. Define infinite width threshold network
Fr(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] dw̃.
For any ‖x‖ ≤ 1, F∞ = f and ∣∣f(x)− Fr(x)∣∣ ≤ 4π ∫‖w‖>r ‖w‖ · |f̂(w)|dw.
2. Define infinite width ReLU network
Qr(x) := f(0) +
∫ |f̂(w)| [ cos(2π(θf (w)− ‖w‖))− 2π‖w‖ sin(2π(θf (w)− ‖w‖)) ] dw
+ xT ∫ w|f̂(w)|dw
+ 4π2 ∫ σ(w̃Tx̃)|f̂(w)| cos(2π(‖w‖ − b))1[|b| ≤ ‖w‖ ≤ r] dw̃.
For any ‖x‖ ≤ 1, Q∞ = f and ∣∣f(x)−Qr(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 : Rd → R be given with Fourier transform f̂ . For any r ∈ [0,∞], define transport mapping Tr(w, b) := (0, . . . , 0, pr(w̃)) with
Tr(w, b)d+1 = pr(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) = Ew̃ 〈 T∞(w̃),Φ(x; w̃) 〉 , and
sup w̃ ‖Tr(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 supw̃ ‖Tr(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 Tr(w, b) := (0, . . . , 0, pr(w̃)) with
Tr(w, b)d+1 = pr(w̃) := 2 [ fα(0) + ∫ |f̂α(v)| cos(2π(θfα(v)− ‖v‖)) dv ] + 2π(2πφ2)(d+1)/2|f̂(φw)|eb
2/2 sin(2π(θfα(φw)− b))1[|b| ≤ ‖w‖ ≤ r]. Then fα(x) = Ew̃ 〈 T∞(w̃),Φ(x; w̃) 〉 for ‖x‖ ≤ 1, and for r ∈ [ √ d,∞),
sup w̃ ‖Tr(w̃)‖ ≤ 2
[ M + (2πφ2)d/2Mf ( 1 + √ 2π3φ2er 2/2 )] ,
where M := supx |f(x)|, and Mf = 1 when fα = Gα and Mf = ‖f(φ·)‖L1 otherwise, and
sup ‖x‖≤1
∣∣∣f(x)− E 〈Tr(w̃),Φ(x; w̃)〉∣∣∣ ≤ 4π(2πφ2)(d+1)/2Mf (√d+ 3) exp(−(r −√d)2/4) .

heading: 4 APPROXIMATING CONTINUOUS FUNCTIONS
text: 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 : Rd → 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 L1 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 : Rd → 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 : Rd → 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πMf (√d+ 3) (2πα2)(d+1)/2ωf (δ) ) .
Let Gα denote a Gaussian with the preceding variance α2, and let Tr denote the truncated Fourier map constructed in Lemma 3.3 for f|δ ∗Gα, with preceding truncation choice r. Then
sup w̃ ‖Tr(w̃)‖ = Õ
‖f|δ‖5L1 (√ d
δ
)5(d+1) [ √ d
ωf (δ) ]4 , sup ‖x‖≤1
∣∣∣f − Ew̃ 〈Tr(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 Tr 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 Tr 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 : Rd+1 → R with ‖p‖L1 <∞ is a pair (w̃, s) where w̃ is sampled from the probability density |p|/‖p‖L1 , 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 L2(P ) bound in Theorem E.1.
Theorem 4.5 (Simplification of Theorem E.1). Let f : Rd → 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 : Rd+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 ((sj , w̃j))mj=1 drawn from p (cf. Definition 4.4),
sup ‖x‖≤1 ∣∣∣∣∣∣f(x)− c1 + ‖p‖L1 m m∑ j=1 sjσ ′( 〈 w̃j , x 〉 ) ∣∣∣∣∣∣ ≤ 2ωf (δ) + ‖p‖L1√m [ 8 √ d ln(m) + √ ln(1/η) ] .

heading: 5 ABSTRACT TRANSPORT MAPPINGS, AND AN RKHS
text: 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̃〉) dw̃ 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 supw̃ ‖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̃〉) dw̃ = ∫ p(w̃) 〈w̃, x̃〉σ′(〈w̃, x̃〉), and thus build a transport around w̃ 7→ 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 ‖2H = 〈T , T 〉H = ∫ ‖T (w̃)‖22 dG(w̃) = ‖T ‖2L2(G); to justify this Hilbert space, note that it gives rise to the usual kernel product (Cho & Saul, 2009), namely
(x, x′) 7→ Ew̃Φ(x; w̃)TΦ(x′; w̃) = 〈 Φ(x; ·),Φ(x′; ·) 〉 H ,
and moreover our earlier predictors can be written as Ew̃ 〈 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 supw̃ ‖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 TB(w̃) := T (w̃)1 [ ‖T (w̃)‖2 ≤ B ] has
approximation error
sup ‖x‖≤1
∣∣∣〈TB ,Φ(x; ·)〉H − 〈T ,Φ(x; ·)〉H∣∣∣ ≤ ‖T ‖2H √ 2
B2 .
2. The input-truncated transport Tr(w̃) := T (w̃)1[‖w̃‖ ≤ r] with r > √ d has approximation
error
sup ‖x‖≤1
∣∣∣〈Tr,Φ(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.

heading: 6 OPEN PROBLEMS
text: 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., yT(H∞)−1y 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 := supw̃ ‖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.

heading: ACKNOWLEDGEMENTS
text: The authors are grateful for support from the NSF under grant IIS-1750051, and from NVIDIA via a GPU grant.

heading: A TECHNICAL LEMMAS
text: Gaussian Concentration. The following lemma collects a few properties of Gaussian concentration needed throughout. Lemma A.1. Let w ∼ Gd be a standard Gaussian in Rd, 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 7→ ‖w‖ is 1-Lipschitz, meaning∣∣∣‖w‖ −∥∥w′∥∥∣∣∣ ≤∥∥w − w′∥∥ , and since E ‖w‖ < √ d.
3. Note that ∫ ‖w‖>r ‖w‖ dG(w) ≤ ∞∑ i=0 ∫ r+i<‖w‖≤r+i+1 (r + i+ 1) dG(w),
whereas the Gaussian concentration from the preceding part grants
P[‖w‖ > r + i] ≤ exp(−(r + i− √ d)2/2) ≤ exp(−(r − √ d)2/2) exp(−i2/2),
whereby∫ ‖w‖>r ‖w‖ dG(w) ≤ (r + 1) ∫ ‖w‖>r dG(w) + ∞∑ i=0 i ∫ ‖w‖>r+i dG(w)
≤ (r + 1) exp(−(r − √ d)2/2) + ∞∑ i=0 i exp(−(r − √ d)2/2) exp(−i2/2)
≤ exp(−(r − √ d)2/2) r + 1 + ∞∑ i=0 i exp(−i2/2)  ≤ exp(−(r − √ d)2/2) [r + 2] .
The final inequality follows by applying Lemma A.2 with (a, b, c, x) = (3, √ d, 2, r)
4. Proceeding similarly,∫ ‖w‖>r ‖w‖ dG(w) ≤ ∞∑ i=0 ∫ r+i<‖w‖≤r+i+1 (r + i+ 1)2 dG(w),
≤ 2(r + 1)2 ∫ ‖w‖>r dG(w) + 2 ∞∑ i=0 i2 ∫ ‖w‖>r+i dG(w)
≤ 2(r + 1)2 exp(−(r − √ d)2/2) + 2 ∞∑ i=0 i2 exp(−(r − √ d)2/2) exp(−i2/2)
≤ 2 exp(−(r − √ d)2/2) (r + 1)2 + ∞∑ i=0 i2 exp(−i2/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πiwTx) 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̂ ĝ and |f̂ ∗ g| ≤ ‖f‖L1 |ĝ|.
3. Let α > 0 be given and define φ := (2πα)−1. Then |Ĝα| = Ĝα (meaning Ĝα has no radial component, thus θGα(w) = 0), and
Ĝα(w) = (2πα 2)−d/2Gφ(w) = (2πφ 2)d/2Gφ(w) = (2π) d/2G(w/φ).
Proof. 1. Directly,
|ĥ(w)| ≤ ∫ |h(x)| · | exp(2πiwTx)|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 Ĝα 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)|z0 − ( bf ′(b)|z0 − ∫ z 0 f ′(b) db ) = zf ′(z)− zf ′(0)− ( zf ′(z)− 0− f(z) + f(0)
) = f(z).

heading: B SAMPLING TOOLS: MAUREY’S LEMMA AND CO-VC DIMENSION
text: 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)mj=1 ∥∥∥∥∥∥f − 1m ∑ j gj ∥∥∥∥∥∥ 2
L2(P )
= 1
m2 E
(vj)mj=1 ∥∥∥∥∥∥ ∑ j ( f − gj )∥∥∥∥∥∥ 2
L2(P )
= 1
m2 E
(vj)mj=1 ∑ j ∥∥f − gj∥∥2L2(P ) = 1
m E v1 ‖f − g1‖2L2(P )
= 1
m E v1
( ‖g1‖2L2(P ) −‖f‖ 2 L2(P ) ) ≤ 1 m Ev1‖g1‖ 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 ((v1, . . . , vm)) = ∥∥∥∥∥∥f − 1m ∑ j g(·; vj) ∥∥∥∥∥∥ L2(P ) ,
and note from the general metric space inequality ∣∣‖p‖ − ‖q‖∣∣ ≤ ‖p − q‖ that for any V = (v1, . . . , vm) and V ′ = (v′1, . . . , v ′ m) differing only on a single vk 6= v′k,
∥∥F (V )− F (V ′)∥∥ ≤ ∥∥∥∥∥∥ 1m ∑ j g(·; vj)− 1 m ∑ j g(·; v′j) ∥∥∥∥∥∥ L2(P )
= 1
m ∥∥g(·; vk)− g(·; v′k)∥∥L2(P ) ≤ 1 m
(∥∥g(·; vk)∥∥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 ) ≤ EV F (V ) + sup v∈V ‖g(·; v)‖L2(P )
√ 2 ln(1/η)
m ,
and the statement follows by Jensen’s inequality, specifically EV F (V ) ≤ √ EV 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̃〉) dw̃ be given with ‖p‖L1 < ∞ and p is supported on a ball of radius B, and let ((sj , w̃j))mj=1 be sampled from p as in Definition 4.4, and define gj(x) := g(〈w̃, x̃〉). With probability at least 1− η,∥∥∥∥∥∥f − ‖p‖L1m m∑ j=1 sjgj ∥∥∥∥∥∥ L2(P ) ≤ sup ‖w̃‖≤B ‖g(〈w̃, ·〉)‖L2(P )‖p‖L1 [ 1 + √ 2 ln(1/η)√ m ] .
Proof. Since∫ p(w̃)g(〈w̃, x̃〉) dw̃ = ‖p‖L1 ∫ sgn(p)
|p(w̃)| ‖p‖L1 g(〈w̃, x̃〉) dw̃ = ‖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‖L1m m∑ j=1 sjgj ∥∥∥∥∥∥ L2(P ) = ‖p‖L1 ∥∥∥∥∥∥Es,w̃sg(〈w̃, ·〉)− 1m m∑ j=1 sjgj ∥∥∥∥∥∥ L2(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 L2(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 : Rd+1 → R with ‖p‖L1 <∞, and let ((sj , wj))mj=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̃〉) dw̃ − ‖p‖L1 m ∑ j sjσ ′( 〈 w̃j , x̃ 〉 ) ∣∣∣∣∣∣ ≤ ‖p‖L1√m [√ 8(d+ 1) ln(m+ 1) + √ ln(1/η) ] .
2. Suppose p is supported on the set W := {w̃ ∈ Rd+1 : ‖w‖ ≤ r, |b| ≤ ‖w‖}. With probability at least 1− 2η,
sup ‖x‖≤1 ∣∣∣∣∣∣ ∫ p(w̃)σ(〈w̃, x̃〉) dw̃ − ‖p‖L1 m ∑ j sjσ( 〈 w̃j , 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̃〉) dw̃ − ‖p‖L1 m ∑ j sjg( 〈 w̃j , x̃ 〉 ) ∣∣∣∣∣∣ = ‖p‖L1 sup
‖x‖≤1 ∣∣∣∣∣∣Ep sg(〈w̃, x̃〉) dw̃ − 1m ∑ j sjg( 〈 w̃j , 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 ∣∣∣∣∣∣Ep sg(〈w̃, x̃〉) dw̃ − 1m ∑ j sjg( 〈 w̃j , x̃ 〉 ) ∣∣∣∣∣∣ ≤ 2Rad ({ (sjg( 〈 w̃j , x̃ 〉 ))mj=1 : ‖x‖ ≤ 1 })
+ 3 sup w̃∈W ‖x‖≤1
|g(〈w̃, x̃〉)| √ ln(1/η)
2m .
whereW is a constraint set on w̃ (when g = σ′, it is Rd+1, whereas with g = σ it is |b| ≤ ‖w‖ ≤ r). To simplify further, note that a Rademacher random vector ( 1, . . . , m) is distributionally equivalent to (s1 1, . . . , sm m) for any fixed vector of signs (s1, . . . , sm), and therefore
Rad ({ (sjg( 〈 w̃j , x̃ 〉 ))mj=1 : ‖x‖ ≤ 1 }) = 1
n E sup ‖x‖≤1 ∑ j sj jg(〈w̃, x̃〉)
= 1
n E sup ‖x‖≤1 ∑ j jg(〈w̃, x̃〉)
= Rad ({ (g( 〈 w̃j , x̃ 〉 ))mj=1 : ‖x‖ ≤ 1 }) .
Combining these steps, with probability at least 1− 2η,
sup ‖x‖≤1 ∣∣∣∣∣∣ ∫ p(w̃)g(〈w̃, x̃〉) dw̃ − ‖p‖L1 m ∑ j sjg( 〈 w̃j , x̃ 〉 ) ∣∣∣∣∣∣ ≤ ‖p‖L1
2Rad({(g(〈w̃j , x̃〉))mj=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 ({ (σ′( 〈 w̃j , x̃ 〉 ))mj=1 : ‖x‖ ≤ 1 }) ≤ √ 2(d+ 1) ln(m+ 1)
m .
2. In the case g = σ, sinceW := {w̃ ∈ Rd+1 : ‖w‖ ≤ r, |b| ≤ ‖w‖}, sup w̃∈W ‖x‖≤1
|σ(〈w̃, x̃〉)| ≤ sup ‖w‖≤r |b|≤‖w‖ ‖x‖≤1 |wTx+ 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 ({ (σ′( 〈 w̃j , x̃ 〉 ))mj=1 : ‖x‖ ≤ 1 }) ≤ Rad ({ ( 〈 w̃j , x̃ 〉 )mj=1 : ‖x‖ ≤ 1 }) ≤ 4r√
m .

heading: C DEFERRED PROOFS FROM SECTION 2
text: 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(·) 〉 − Ew̃ 〈 T (w̃),Φ(·; w̃) 〉∥∥∥∥∥∥ L2(P ) ≤ B [√ 2 + 2 √ ln(1/η) ] .
Proof. The proof proceeds by applying Maurey sampling (cf. Lemma 2.5) to the functions gj(x) := m 〈 τj , φj(x) 〉 , noting by Lemma 2.4 that
f(x) := E W̃ ,S
1
m ∑ j gj(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 − 1m m∑ j=1 gj ∥∥∥∥∥∥ L2(P ) ≤ supw̃,sm‖ 〈 T (w̃, s),Φ (·; w̃, s) 〉 ‖L2(P )√ m [ 1 + √ 2 ln(1/η) ] ,
where
sup w̃,s ‖ 〈 T (w̃, s),Φ (·; w̃, s) 〉 ‖2L2(P ) ≤ sup w̃,s Ex ∥∥T (w̃)∥∥22∥∥Φ (x; w̃, s)∥∥22 ≤ 2 2B2 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 sj √ 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̃〉) 6= 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̃〉) 6= sgn( 〈 T ′ (w̃), x̃ 〉 ) ]
≤ P̃ w
[ | 〈w̃, x̃〉 | ≤ B‖x̃‖/ √m ] = P̃
w
[ |w1| · ‖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 gj(x) := g(x; w̃j , sj). Using this notation, the goal of this proof is to upper bound∥∥∥∥∥∥ ∑ j 〈 τj , φj(·) 〉 − ∑ j sj √ m σ( 〈 τj , · 〉 ) ∥∥∥∥∥∥ L2(P ) = ∥∥∥∥∥∥ 1m ∑ j gj ∥∥∥∥∥∥ L2(P ) . By Lemma 2.5, with probability at least 1− η,∥∥∥∥∥∥ 1m ∑ j gj ∥∥∥∥∥∥ L2(P ) ≤ ‖f‖L2(P ) + ∥∥∥∥∥∥f − 1m ∑ j gj ∥∥∥∥∥∥ 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 ) = m2 E x 〈 T (w̃, s),Φ (x; w̃, s)− s √ m Φ(x; T (w̃, s)) 〉2 ≤ m2B2 E x 2‖x‖2 m ≤ 2m 2B2 .
On the other hand, by Lemma 2.6, for any ‖x‖ ≤ 1,
|f(x)| ≤ Ew̃,s ∣∣∣∣∣ 〈 T (w̃, s),Φ (x; w̃, s)− s √ m Φ(x; T (w̃, s)) 〉∣∣∣∣∣
≤ B Ew̃,s ‖x̃‖ ∣∣σ′(T (w̃)Tx̃)− σ′(w̃Tx̃)∣∣√ m
≤ B √ m
( B
√ mπ
) ,
which also upper bounds ‖f‖L2(P ).
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 (w̃1, . . . , w̃m), maxj ‖w̃j‖ ≤ R, thus
max j ‖T (w̃j)− w̃j‖ ≤ max j ‖T (w̃j)‖ √ m ≤ B √ m .
Moreover, R ≥ √ d+ 2 √ ln ( √ mπ
B √ 2
) , and thus the two other bounds are from Lemmas C.1 and C.2.

heading: D DEFERRED PROOFS FROM SECTION 3
text: 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πixTw)f̂(w) dw
= Re ∫ exp(2πixTw + 2πiθf (w))|f̂(w)|dw
= ∫ cos ( 2π(xTw + θf (w)) ) |f̂(w)|dw.
For convenience, define h(z) := cos(2πz), whereby f(x)− f(0) = ∫ h(xTw + θ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[xTw + b ≥ 0]1[‖w‖ ≥ b] db, b 7→ θf (w)− b
= − ∫ h′(θf (w)− b)1[xTw + b ≥ 0]1[‖w‖ ≥ |b|] db,
where the last step follows since 1[xTw + 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π(xTw + θf (w)) ) dw
= ∫ |f̂(w)| [ h(−‖w‖+ θf (w))− ∫ h′(θf (w)− b)1[xTw + 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[xTw + b ≥ 0]1[‖w‖ ≥ |b|] dbdw
= 2π ∫ |f̂(w)| sin(2π(θf (w)− b))σ′(〈w̃, x̃〉)1[‖w‖ ≥ |b|] dw̃,
which gives F∞ = f for ‖x‖ ≤ 1. To bound the error of Fr, note by the form of F∞ for any ‖x‖ ≤ 1 that ∣∣f(x)− Fr(x)∣∣ = ∣∣∣∣∣2π ∫ ‖w‖>r ∫ |f̂(w)| sin(2π(θf (w)− b))σ′(〈w̃, x̃〉)1[‖w‖ ≥ |b|] dbdw
∣∣∣∣∣ ≤ 2π
∫ ‖w‖>r ∫ |b|≤‖w‖ |f̂(w)|| sin(2π(θf (w)− b))|σ′(〈w̃, x̃〉) dbdw
≤ 2π ∫ ‖w‖>r |f̂(w)| ∫ |b|≤‖w‖ dbdw
= 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 := wTx + θ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)σ(wTx+ θf (w) + ‖w‖ − θf (w)− b)1[b ≥ 0] db
= − ∫ H ′′(‖w‖ − b)σ(wTx+ b)1[‖w‖ ≥ b] db b 7→ ‖w‖ − b
= − ∫ H ′′(‖w‖ − b)σ(wTx+ b)1[‖w‖ ≥ |b|] db,
the final equality since −b > ‖w‖ implies wTx+ b ≤ ‖w‖+ b < 0, thus σ(w̃Tx̃) = 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)σ(w̃Tx̃)1[‖w‖ ≥ |b|] db ] dw
= ∫ |f̂(w)| [ h(q) + (wTx+ ‖w‖)h′(q)− ∫ H ′′(‖w‖ − b)σ(w̃Tx̃)1[‖w‖ ≥ |b|] db ] dw,
which gives Q∞ = f for ‖x‖ ≤ 1 after expanding h and H . To bound the error of Qr, for any ‖x‖ ≤ 1
∣∣f(x)−Qr(x)∣∣ = ∣∣∣∣∣ ∫ ‖w‖>r |f̂(w)| ∫ H ′′(‖w‖ − b)σ(w̃Tx̃)1[‖w‖ ≥ |b|] db ∣∣∣∣∣ dw ≤ ∫ ‖w‖>r |f̂(w)| ∫ |H ′′(‖w‖ − b)|σ(w̃Tx̃)1[‖w‖ ≥ |b|] dbdw
≤ 4π2 ∫ ‖w‖>r |f̂(w)| ∫ ‖w‖ −‖w‖ σ(w̃Tx̃) dbdw
≤ 4π2 ∫ ‖w‖>r |f̂(w)| ∫ ‖w‖ −‖w‖ (‖w‖+ |b|) dbdw
≤ 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[xTw + b ≥ 0]1[‖w‖ ≥ |b|] dbdw
= − ∫ |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[w̃Tx̃ ≥ 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̃)) ∈ Rd × 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, Ew̃ 〈 Tr(w̃),Φ(x; w̃) 〉 = Fr(x), and therefore Lemma 3.1 grants for all ‖x‖ ≤ 1 f(x) = Ew̃ 〈 T∞(w̃),Φ(x; w̃) 〉 and ∣∣∣f(x)− E 〈Tr(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)|Ĝα(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 introduceG(w̃), and then manually introducing
G(b), fα(x)− fα(0)− ∫ |f̂α(w)|h(θfα(w)− ‖w‖) dw
= − ∫∫ |f̂α(w)|h′(θfα(w)− b)σ′(w̃Tx̃)1[‖w‖ ≥ |b|] dbdw
= −(2π)d/2 ∫∫ |f̂(w)|G(w/φ)h′(θfα(w)− b)σ′(w̃Tx̃)1[‖w‖ ≥ |b|] dbdw
= −(2πφ2)d/2φ ∫ |f̂(φw)|G(w)h′(θfα(φw)− b)σ′(φ 〈w̃, x̃〉)1[φ‖w‖ ≥ φ|b|] dbdw
= −(2πφ2)(d+1)/2 ∫ |f̂(φw)|eb
2/2h′(θ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: Tr(w, b) = (0, . . . , 0, pr(w̃)), where
pr(w̃) := 2 [ fα(0) + ∫ |f̂α(v)|h(θfα(v)− ‖v‖) dv ] − (2πφ2)(d+1)/2|f̂(φw)|eb 2/2h′(θfα(φw)− b)1 [ |b| ≤ ‖w‖ ≤ r ] ,
with f(x) = Ew̃ 〈 T∞(w̃),Φ(x; w̃) 〉 for ‖x‖ ≤ 1 by construction.
When r <∞, by construction
sup w̃ ‖Tr(w̃)‖ ≤ 2 ∣∣fα(0)∣∣+ 2 ∫ |f̂α(v)|dv + 2π(2πφ2)(d+1)/2 sup ‖w‖≤r |b|≤‖w‖ |f̂(φw)|eb 2/2,
where |f̂(φw)| = 1 when fα = Gα (meaning f itself 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)| ≤Mf . Plugging this in and simplifying further via Lemma A.3,
sup w̃ ‖Tr(w̃)‖ ≤ 2 ∣∣∣∣∫ f(x)Gα(−x) dx∣∣∣∣+ 2(2π)d/2 ∫ |f̂(v)|G(v/φ) dv + 2π(2πφ2)(d+1)/2Mf sup |b|≤r eb 2/2
≤ 2 [ M + 2(2πφ2)d/2Mf + 2π(2πφ
2)(d+1)/2Mf sup |b|≤r
eb 2/2 ] .
For the approximation estimate, for any ‖x‖ ≤ 1, the preceding derivation and Lemma A.1 grant∣∣∣f(x)− E 〈Tr(w̃),Φ(x; w̃)〉∣∣∣ = ∣∣∣E 〈T∞(w̃)− Tr(w̃),Φ(x; w̃)〉∣∣∣ ≤ 2π(2πφ2)(d+1)/2
∫ ‖w‖>r ∫ |b|≤‖w‖ |f̂(φw)|| sin(2π(wTx+ θfα(w)))σ′(w̃Tx̃)|dbdG(w)
≤ 2π(2πφ2)(d+1)/2Mf ∫ ‖w‖>r ∫ |b|≤‖w‖ dbdG(w)
≤ 4π(2πφ2)(d+1)/2Mf ∫ ‖w‖>r ‖w‖ dG(w) ≤ 4π(2πφ2)(d+1)/2Mf ( √ d+ 3) exp ( −(r − √ d)2/4 ) .

heading: E DEFERRED PROOFS FROM SECTION 4
text: 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 〈Tr(w̃),Φ(x; w̃)〉∣∣∣ ≤ 4π(2πφ2)(d+1)/2Mf (√d+ 3) exp(−(r −√d)2/4) ≤ ωf (δ). Moreover, plugging r into the estimate on supw̃ ‖Tr(w̃)‖ provided by Lemma 3.3 gives
sup w̃ ‖Tr(w̃)‖ ≤ 2
[ M + (2πφ2)d/2Mf ( 1 + √ 2π3φ2er 2/2 )] ,
where Lemma A.3 and the choice of r give
Mf ≤ ‖f|δ‖L1 , and er 2/2 ≤ ede(r−
√ d)2 ,
where
e(r− √ d)2 =
( 4π(2πφ2)(d+1)/2Mf ( √ d+ 3)
ωf (δ)
)4 = O ( Mf√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 : Rd → 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 ĥ satisfying radial decomposition ĥ(w) = |ĥ(w)| exp(2πiθh(w). Lastly, let P be a probability measure supported on ‖x‖ ≤ 1.
1. Additionally define
c1 := h(0)+
∫ |ĥ(w)| cos ( 2π(θh(w)− ‖w‖) ) dw, p1 := 2π|ĥ(w)| sin(2π(θh(w)−b))1 [ |b| ≤ ‖w‖ ] .
Then
|c1| ≤M + ‖f|δ‖L1(2πα2)d/2, and ‖p1‖L1 ≤ 2‖f|δ‖L1
√ 2πd
(2πα2)d+1 ,
and with probability at least 1−3η over a draw of ((sj , w̃j))mj=1 from p1 (cf. Definition 4.4),∥∥∥∥∥∥f − c1 + ‖p1‖L1 m∑
j=1
sjσ ′( 〈 w̃j , · 〉 ) ∥∥∥∥∥∥ L2(P ) ≤ 2ωf (δ) + ‖p1‖L1 [ 1 + √ 2 ln(1/η)√ m ] ,
sup ‖x‖≤1 ∣∣∣∣∣∣f(x)− c1 + ‖p1‖L1 m∑
j=1
sjσ ′( 〈 w̃j , x 〉 ) ∣∣∣∣∣∣ ≤ 2ωf (δ) + ‖p‖L1√m [√ 8(d+ 1) ln(m+ 1) + √ ln(1/η) ] .
2. Additionally define
c2 := f(0)f(0) +
∫ |ĥ(w)| [ cos(2π(θh(w)− ‖w‖))− 2π‖w‖ sin(2π(θh(w)− ‖w‖)) ] dw,
a2 :=
∫ w|ĥ(w)|dw,
r2 := √ d+ 2 √ ln
24π2( √ d+ 7)2‖f|δ‖L1 ωf (δ) ,
p2(w̃) := 4π 2|ĥ(w)| cos(2π(‖w‖ − b))1[|b| ≤ ‖w‖ ≤ r2],
and for convenience create fake (weight, bias, sign) triples
(w, b, s)m+1 := (0, |c2|,m · sgn(c2)), (w, b, s)m+2 := (a2, 0,+m), (w, b, s)m+3 := (−a2, 0,−m).
Then
‖a2‖2 ≤ √ d‖f|δ‖L1φ(2πα2)−d/2,
‖p2‖L1 ≤ 2‖f|δ‖L1
√ (2π)3d
(2πα2)d+1 ,
|c2| ≤M + 2 √ d‖f|δ‖L1(2πα2)−d/2,
and with probability at least 1−3η over a draw of ((sj , w̃j))mj=1 from p2 (cf. Definition 4.4),∥∥∥∥∥∥f − 1m m+3∑ j=1 sjσ( 〈 w̃j , · 〉 ) ∥∥∥∥∥∥ L2(P ) ≤ 3ωf (δ) + r2‖p‖L1 [ 1 + √ 2 ln(1/η)√ m ] ,
sup ‖x‖≤1 ∣∣∣∣∣∣f(x)− 1m m+3∑ j=1 sjσ( 〈 w̃j , · 〉 ) ∣∣∣∣∣∣ ≤ 3ωf (δ) + 4r2‖p‖L1√m [ 1 + √ ln(1/η) ] .
Proof. 1. By Lemma 3.1 and the choice of b1, for any ‖x‖ ≤ 1,
h(x) = c1 + ∫ p1(w̃)σ ′(〈w̃, x〉) dw̃,
thus by Lemma 4.2 and Lemma B.1, defining hj := ‖p‖L1σ′( 〈 w̃j , · 〉 ) for convenience, with
probability at least 1− η,∥∥∥∥∥∥f − (c1 + ∑ j hj/m) ∥∥∥∥∥∥ L2(P ) ≤‖f − h‖L2(P ) + ∥∥∥∥∥∥h− (c1 + ∑ j hj/m) ∥∥∥∥∥∥ L2(P )
≤ 2ωf (δ) + ‖p1‖L1 sup ‖w̃‖≤r2 ‖σ′(〈w̃, ·〉 ‖L2(P )
[ 1 + √ 2 ln(1/η)√ m ]
≤ 2ωf (δ) + ‖p1‖L1
[ 1 + √ 2 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)− (c1 + ∑ j hj(x)/m) ∣∣∣∣∣∣ ≤ ∣∣f(x)− h(x)∣∣+ ∣∣∣∣∣∣h(x)− (c1 + ∑ j hj(x)/m) ∣∣∣∣∣∣ ≤ 2ωf (δ) +
‖p1‖L1√ m
[√ 8(d+ 1) ln(m+ 1) + √ ln(1/η) ] .
For the estimates on |c1| and ‖p1‖L1 , note setting φ := (2πα)−1, note by Lemma A.3 and a change of variable w 7→ φw and Lemma A.1 that
‖p1‖L1 ≤ 2π ∫ | ̂f|δ ∗Gα(w)| ∫ 1[|b| ≤ ‖w‖] dbdw
≤ 4π‖f|δ‖L1 ∫ ‖w‖(2πφ2)d/2Gφ(w) dw
= 4π(2π)d/2‖f|δ‖L1 ∫ ‖φw‖φdG(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,
|c1| ≤M + ‖f|δ‖L1 ∫ Ĝα(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,∣∣∣∣b2 + 〈x, a2〉+ ∫ p2(w̃)σ(〈w̃, x〉) dw̃ − h(x)∣∣∣∣ ≤ 12π2 ∫ ‖w‖>r2 ‖w‖2|ĥ(w)|dw
≤ 24π2( √ d+ 7)2 exp(−(r2 − √ d)2/4)
≤ ωf (δ). Thus by Lemma 4.2 and Lemma B.1, defining hj := ‖p‖L1sjσ( 〈 w̃j , · 〉 ) for convenience,
with probability at least 1− η,∥∥∥∥∥∥f − m+3∑ j=1 hj/m ∥∥∥∥∥∥ L2(P ) ≤‖f − h‖L2(P ) + ∥∥f − (b2 + (·)Tc2 + Ep2s1h1∥∥+ ∥∥∥∥∥∥Ep2s1h1 − m∑ j=1 sjhj/m ∥∥∥∥∥∥ L2(P )
≤ 3ωf (δ) + ‖p2‖L1 sup ‖w̃‖≤r2 ‖σ(〈w̃, ·〉 ‖L2(P )
[ 1 + √ 2 ln(1/η)√ m ]
≤ 3ωf (δ) + 2r2‖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 hj(x)/m ∣∣∣∣∣∣ ≤ ∣∣f(x)− h(x)∣∣+∣∣f(x)− (b2 + xTc2 + Ep2s1h1(x)∣∣+ ∣∣∣∣∣∣Ep2 s1h1(x)− m∑ j=1 sjhj(x)/m ∣∣∣∣∣∣ ≤ 3ωf (δ) +
4r2‖p2‖L1√ m
[ 1 + √ ln(1/η) ] .
For the estimates on |c1| and ‖p1‖L1 , note setting φ := (2πα)−1, note by Lemma A.3 and a change of variable w 7→ φw and Lemma A.1 that
‖p2‖L1 ≤ 4π2 ∫ | ̂f|δ ∗Gα(w)| ∫ 1[|b| ≤ ‖w‖ ≤ r2] dbdw
≤ 8π2‖f|δ‖L1 ∫ ‖w‖≤r2 ‖w‖(2πφ2)d/2Gφ(w) dw
= 8π2(2π)d/2‖f|δ‖L1 ∫ ‖φw‖≤r2 ‖φw‖φdG(w) dw
≤ 8π2(2π)d/2φd+1‖f|δ‖L1 ∫ ‖φw‖≤r2 ‖w‖G(w) dw ≤ 8 √ dπ2(2π)d/2φd+1‖f|δ‖L1
≤ 2‖f|δ‖L1
√ (2π)3d
(2πα2)d+1 .
Similarly,
|c2| ≤M + ‖f|δ‖L1 ∫ (1 + ‖w‖)Ĝα(w) dw
≤M + ‖f|δ‖L1(2πφ2)d/2 ∫ (1 + ‖φw‖) dG(w) ≤M + 2 √ d‖f|δ‖L1(2πφ2)d/2,
‖a2‖2 = ∥∥∥∥∫ w|ĥ(w)|dw∥∥∥∥ ≤ ∫ ‖w‖|ĥ(w)|dw
≤ ‖f|δ‖L1(2πφ2)d/2 ∫ ‖φw‖|ĥ(w)|dw ≤ √ d‖f|δ‖L1φ(2πφ2)d/2.

heading: F DEFERRED PROOFS FROM SECTION 5
text: Lastly, the two short proofs leading to the RKHS bounds.
Proof of Proposition 5.1. 1. By Markov’s inequality∫ 1[‖T (w̃)‖2 > B] dG(w̃) ≤
‖T ‖2H B2 ,
thus by Cauchy-Schwarz, for any ‖x‖ ≤ 1,∣∣∣〈TB ,Φ(x; ·)〉H − 〈T ,Φ(x; ·)〉H∣∣∣ = ∣∣∣∣∫ (TB(w̃)− T (w̃))T x̃σ′(〈w̃, x̃〉) dG(w̃)∣∣∣∣ ≤ ∫ ∣∣∣1 [‖T (w̃)‖2 > B]∣∣∣ ·∣∣T (w̃)Tx̃∣∣ ·∣∣σ′(〈w̃, x̃〉)∣∣dG(w̃)
≤ √∫ 1 [ ‖T (w̃)‖2 > B ]2 dG(w̃) · √∫ ( T (w̃)Tx̃ )2 dG(w̃)
≤ ‖T ‖H B ·
√∫ 2‖T (w̃)‖2 dG(w̃)
= ‖T ‖2H
√ 2
B .
2. Proceeding similarly, but now using Lemma A.1 to control the indicator,∣∣∣〈Tr,Φ(x; ·)〉H − 〈T ,Φ(x; ·)〉H∣∣∣ = ∣∣∣∣∫ (Tr(w̃)− T (w̃))T x̃σ′(〈w̃, x̃〉) dG(w̃)∣∣∣∣ ≤ ∫ ∣∣∣1 [‖w̃‖2 > r]∣∣∣ ·∣∣T (w̃)Tx̃∣∣ ·∣∣σ′(〈w̃, x̃〉)∣∣dG(w̃)
≤ √∫ 1 [ ‖w̃‖2 > r ]2 dG(w̃) · √∫ ( T (w̃)Tx̃ )2 dG(w̃) ≤ √ exp ( −(r − √ d)2/2 ) · √∫ 2‖T (w̃)‖2 dG(w̃)
= ‖T ‖H
√ 2
e(r− √ d)2/4 .

Review summaries:
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).