Neural tangent kernels, transportation mappings, and universal approximation
Authors: Ziwei Ji
Matus Telgarsky
Ruicheng Xian
Venue:  (2020)
Keywords: Neural Tangent Kernel
universal approximation
Barron
transport mapping

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 / \delta^{10d}$ nodes are sufficient to approximate continuous functions, where $\delta$ depends on the continuity properties of the target function. By contrast, nearly the same proof yields a bound of $1 / \delta^{2d}$ for shallow ReLU networks; this gap suggests a tantalizing direction for future work, separating shallow ReLU networks and their linearization.


Published as a conference paper at ICLR 2020
NEURAL TANGENT KERNELS, TRANSPORTATION MAP- PINGS, AND UNIVERSAL APPROXIMATION
Ziwei Ji, Matus Telgarsky, Ruicheng Xian
Department of Computer Science University of Illinois at Urbana-Chama Urbana-Champaign
2iwei j12
m m rxian2 1 eillinois.dd
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 linearization. Concretely, the paper has two main contributions: a generic scheme to upproximate 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. Regard- ing 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/8t04 nodes are sufficient to approximate continuous functions, where 5 depends on the continuity properties of the target function. By contrast, nearly the same proof yields bound of 1/224 for shallow ReLU networks; this gap suggests a tantalizing direction for future work, separating shallow ReLU networks and their lincarization.
MAIN RESULT AND OVERVIEW
Consider functions computed by a single ReLU layer, meaning
850 ((w5, by). bb))
(1.1)
where (=2) max max(0,2) 20. 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 these networks, and they generalize (Zhang 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.) (0188) Du et al.) 2018 Allen-Zhu et al. 2018), which replaces a network with its linearization at initialization, meaning
9j (Tz, (T,, ((ū), where E (z, 1) e Rd+1, w = (w, b) e Rd-1; (1.2)
1=1
here each viy (wy, by) is frozen at Gaussian initialization (henceforth the bias is collapsed for convenience), and each transported weight Tj is microscopically close to the corresponding initial weight Wj. concretely ||T, - w, (1/emm)) where e is a parameter and the scaling s/vm is conventional in this literature (Allen-Zhu al. 2018).
As eq. 1.2 merely affine in the parameters,
not outlandish that gradient descent can be
analyzed. What is outlandish is firstly that gradient descent eq. (1.1) with small learning rate will track the behavior of eq. (I.2), and secondly the weights hardly change as a function of m, specifically ||T; W5اl2 Ol)/mm).

---

Published as a conference paper at ICLR 2020
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 T| wy || = (1/em)) In more detail:
Contributions.
Continuous functions (ef. 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/6ind, where 8 depends on continuity properties of the target function: moreover, the transports satisfy ||T ررن = ((/em),, 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/824 is exhibited for ReLU networks in Theorem E. 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 Theo-
rem I.3] 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 ||T الرlة = O())mm) 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 Gaussian Ga with tiny variance a². Care is needed in order obtain a rate of the form 1/8000 rather than, say, 1/8016/5) 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 and abstract approaches to constructing transport mappings, including ones
Section 3 (ection[5]skeetteee 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: IR++1 - Rd+1 to show where weights should go:
+ E,g (T(i)), (1;; w) E. (T(m), .)) o ((wi R)) FP (T 5))
(1ū, 8) 2 0].
where ((x; áoo (000000'000 ((w) R)) is random feature representation of x (Rahimi & Recht 2008). This abstracts the individual transported weights (r from before into transported weights defined over arbitrary weights w e Rd+1, These (augmented) weights v = (w, 6) (with weight w e R and bias 6 E R) will always be distributed according standard Gaussian with identity covariance. with G denoting the density and probability law simultaneously.
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 E [-1,+1] denote a uniformly distributed random sign,
(Tw)), 4 (2; i)
E. (T2((1)
()) + swe m, +x ())
E = 1,
T( + sgú EV m, D(:; w,))
sampling (wy, 85) (1.3)
m
m
8, c\m m
w. 8, 3,;
2

---

Published as a conference paper at ICLR 2020
As highlighted by the bolded terms: increasing the width corresponds to resampling, and allows the transported weights to be scaled down! Indeed, the distance moved is ((/ev/) by construction. To this end, for convenience define
== Te((ū = 8TT(W;)
111ا1 - RJ,
c/m
(1.4)
(x = ee; wy 85) = CS
4 (z; wy = ES To ((ū),
vm
where R is a truncation radius included for purely technical reasons. The transport mappings
constructed in Section 3 satisfy B == sup, [[[ co, and thus maxy ||z النl Bleym by
construction as promised (with high probability).
The key message of Section is to control the deviations of this process, culminating in Theorem 2.1 and also Theorem [.5 below, which yields upper bounds on the width necessary to approximate infinite width networks. The notion of approximation here will follow (Barron (993) and the (P) metric, where P is a probability measure on the ball {a E R : |
[hlleg()) - / Mo))dP())
Additionally ||b||r2 - (f dz dx and ||0||e, = [h(x)] da 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 funciton f R R be given.
S 8 and max [| ||='||] S 1+8. Let be any probability distribution over | S Then there exists a transport mapping T (defining
along with 5 E (0, 1] so that f(z)) I whenever
Te and Tj as in eq. (1.4) and associated scalurs
T ()) =6 M$a2G449)/22
B = sup
where M == sup [f(x)),
c²85(d-1)
111
so that with probability least 1 3n over Gaussian weights (wy)) and uniform signs (8,)7= then max; ||r
W6g B/c./m, and
f- Σ (5)
[
B
+
evd Vinll/m)
12(P)
B²
B +
B vm + tova Vin(i/))
mm Σ 8y0
(T)
- Σ (3,001))
+
cm3/2
1=1
(P(P)
In words: given an arbitrary target function f and associated continuity parameter 8, width (B/e)²= ((aaa= 0(20500/220 (200goot)1)) suffices for error Ö(e), 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 sense robust, and may be used algorithmically!
be extracted and converted into a direct approximation rate of continuous functions by ReLU networks, and the rate becomes +/a4 (a))).))). Since this rate is nearly tight, together these rates pose an interesting question: is there purely approximation-the -hhooreticc gap between shallow ReLU networks and their NTK?
As provided in Theorem 4.5 elements of the proof of Theorem 1.5
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-paralle works
(Jacot et al. 2018 Du al. 2018 Du et al. 2018 Allen-Zhu al. 2018 Arora al. 2019 Oymak
3

---

Published as a conference paper at ICLR 2020
& 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 1/vm. This is consistent with the resampling perspective here, as summarized in eq. (1.))
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 o' d'(W6, g. 2)) 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.33 and for shallow networks in Theorem [. 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, > 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 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/ ʃ : Rd - IR when the associated quantity J |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 | [ww] 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/80 Theorem 4.5 does not seem to appear rigorously in prior work, though it is mentioned as
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 's original proof (Weierstrass) 1885
Many related works RKHSes directly. [Sun al. (018) prove universal approximation (with rates) via an RKHS, however they do not consider the NTK (or the NTK setting of small weight changes). Bach (20 (see also (Bach] 2017b Basri al. 2019 Bietti Mairal 2019)) studies 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 few further conditions); the rates are better than those here (roughly O O(T/84/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 (2(d) derivatives (Ongie et al. 2019); similarly, the constructions here use 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/8d/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/8" 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 infinite width NTK, the resulting finite width NTK is close in (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.
4

---

Published as a conference paper at ICLR 2020
Theorem 2.1. Suppose B 2 max {2, sup& [T] and set R vd+ 1 2 In(m/n). With
probability at least 31, then maxj
[Ty
üūg || S Ble/m, and
(g,00)) - Es (T(w), ((;ū))
S 2
B + tR
I /mm(1/n)
(2.2)
vm
1.(P)
Σ (5))))))) - Σ 856
mm o (TT+)))
$
B
BR
+ +cR) Vm
B
[1+vin((1n))
cm3/2
m
L2(P)
(2.3)
As discussed in the introduction, max, T, Wاl I B/evm is essentially by construction. Next, recall the sampling derivation in eq. [1.3.. restated here as a lemma for convenience, the notation SW, collecting all random variables together, meaning W (w1,..... wmm and 5 ($1,...,, 8m).
Lemma 2.4. E (T(w):
((x; w))
(Te(ū, 8,), De (x üy s5)) W.S
E
Σ (z))). W.S
E
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 (993). The following version additionally includes a high probability control, which results from application of McDiarmid's inequality. Applying the following sampling lemma to the present setting, the deviations will scale with B = sup, II (w) (w)
Lemma 2.5 (Maurey). Let functions (g(:v) v E V) be given, where V C RR is set of possible parameters. Let be a probability measure over V, let (Vi,..., Um) be an iid random draw from v, and define
f(x) = E g(
and 21(x) == 1-=gg(;)))) vz).
Then
m
1 E Elgg(:)) s m se (
f m
9j
((8).%) 1)5m
m
j=1
(P(P))
and with probability least 17.
m
1 22lm(1/n)
I suup suuplo((=))llx(e) vEV
9j
m
m
(P(P)
Concretely, here (1) m (T,, (z)). and sup.ev (lg(;; ()ll(2(P) S sus [ O(B Re by Cauchy-Schwarz. Before continuing, note also that there are other proof schemes attaining similar bounds (Bach 2017a Proposition 1), and that similar bounds are possible for the uniform norm, albeit with more sensitivity to the basis functions g (cf. Lemma (.2).
Turning now to the final bound in eq.
(.. the first step is to note by positive homogeneity of the thus
ReLU that a ((T, +)) (T), (())(())))))))
Σ O))
Σ s (T, -))
T,
9jE 10.00' ((Ty,
Vm
which boils down checking the difference in activations, namely o' o'((ū,, x)) o' ((T,, As is standard in the NTK literature, since T رر is (with high probability) microscopic compared to (wzy Z), the activations should also be close. The following lemma makes this precise.
Lemma 2.6. For any x E RR, if R 2 Vd + 2//2/ in
cemmm BvI
(as used in eq. (1.4), then
2B
B o' ((1 .)) o' (T.
<
c/mm
From here, the eq. (..) 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, || $ R. This also establishes the first half of Theorem L.3
5

---

Published as a conference paper at ICLR 2020
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 variety of transport maps.
The transport mappings here will be constructed via Fourier transforms, with convention
f(x) = / exp (-2wiaa w) f(x) dæ;
/
a few general properties are summarized in Appendix A Interestingly, these transports are all random feature transports: they have the form T( (0..... p(ū)) where p signed density over random features, and Es (w)), 2 [z; w)) Eap(w)o' ((w, Z)). This perspective of 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 (For constructions which not based on random features, see Section
The first steps of the approach here follow derivation due to Barron 1993). Specifically, the inverse Fourier transform gives a way to rewrite function as an infinite with network with complex-valued activations x ++ exp(2mix' w):
f(x) = f exp(2xix" w) (w) dw.
key trick due to Barron 1993) to force the right hand side to be real (since the left hand side real): specifically, letting f(w) = (f(w) (2mi0(((w)) with [0y(w)] I 1 denote the radial decomposition of f.
Ref(x) Re
exp((2ria (1(2mit"))fil ") dw
Re exp(22rix" w + 2 ( (w))) (w)))
/ cos (2m(x"" + (w)))) If (w) dw.
After this step. the proofs diverge: the approach here is to use the fundamental theorem of calculus to rewrite cos terms of a':
/ sin(b) db = =- sin b 0] d6, - - sin (i)bb' (2 6) db;
cos(2) - (Os())
plugging this back in gives 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 summarized in the following lemma, which includes 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 f ||w|| [f() dw,, which was explicitly introduced as key quantity by Barron (1993) via a different route, namely of introducing a factor ||l|| to enforce decay cos.
Lemma 3.1. Let f: Idd + R be given with Fourier transform f and truncation radius r E [0)
1. Define infinite width threshold network
F+(x): = -(0) + [f(w)) cos (2T ||w])) dw
2T /
sin (2m(22200 b]) < ||l||| s dk.
For any |||||| 5 1, Fx. = and f(x) (x)) 4t Snwn ||m||| || (f(w) dw.

---

Published as a conference paper at ICLR 2020
2. Define infinite width ReLU network
Q+(z) = f(0) f [f(w) (cos(2)(0)(w)) |=ll)) 2 (0 - [|]]]))] dw
+ 5t ʃ w/ wlf(wo)] dw
+ +4 f a
[ 8)) cos (2:(( - [|6] z || I r] duū
For any ||]||| 1 Qx - and 1 Si ||w||2 [f() dw.
12
(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 few places in the appendices, but is not part of the main NTK story.)
The preceding constructions immediately yield transport mappings from Gaussian initialization the function f in a brute-force way: by introducing the fraction G(a)/C(()) 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 E o0), define transport mapping T. b) = (O..... .,, 0,pr(1)) with
T, (, ()0,b) (w)) = 2 [(0) / (os) [|ell)) de
[((ww] (os(22(0)(10) b)) [M S ||||| s r].
2x
G(
By this choice, for any ||^||| S f(x) = E. (Too (10), ((;; w) and
[f(w]
sup | (w)l S 2|0 + 2 / [f(v) du + 2n sup
G(ū)
a
|w||s |
/ / [f(w)) || dw.
[(x) E (T (2; m))
S 4m
The preceding construction may seem general, however it is quite loose, noting the final supremum term within sup (w) [2; indeed, attempting to plug this construction into Theorem 2.1 does not yield the 1/)0(() rate in Theorem 1.5 but instead a rate 1/80aaz5), which is disastrously larger!
Interestingly, fix is possible for special functions of the form f G.. namely convolutions with Gaussians of coordinate-wist variance a², These are exactly the types of functions used in Section 4 to approximate continuous functions. The fix is simply to apply change of variable that, in sense, the target function and the initialization distribution have similar units.
Lemma 3.3. Let function f. variance a² > O, and r E [0, oc] be given, and define Sa == f Ga and x == (2xa) and transport mapping Tr b) == (O. (,Pr(1i) with
(((wbb)at = pr)) = (a + / [o) (v) cos (0,, (v) [[-l])) du
2T (2 (d+ (f 0² sin (2 (0,, (ow) - 6))1 S ||l|| S sr..
Then fa(x)= = Ee (Too (w), ((; x) for | S 1, for E [Vd, 20).
sup |T, || < 2 M + (2 d/2 M, (1 (1+ v 2 300 22222212))) 12)]
where M : sup, (x)) and M, when Sa Go and M, [|((()))))l)> otherwise, and
f(x) - E (Tr ()) (<: (<: < 4 (0.)) 3) exp (-(r- vd)21a).
sup |
7

---

Published as a conference paper at ICLR 2020
4 APPROXIMATING CONTINUOUS FUNCTIONS
The final piece needed prove Theorem 1.5 is to show that function f is close to its Gaussian convolution f Go., at least when a is chosen appropriately. This 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 (e.8) conditions associated with continuous functions with an exact quantity.
Definition 4.1. Let R IR be given, and define modulus of continuity w/
( = sup (f(x) - (x²) max [[ [| s 5 5
If f is continuous, then w (defined here over a compact set) is not only finite for all inputs, but moreover ( - 0. It is also possible use this definition with discontinuous functions; note additionally that the convolution bounds in Section 3 only required an I, bound on the pre- convolution 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 RRd R and 8 > 0 be given, and define
5
M == sup [f())), |
=
11+0),
a:
Vdt (21((2M/u5(0)
Let Go denote Gaussian with the preceding variance a? Then
sup |
J/s * G. s 2wy(d).
The proof splits the integrand into two parts: points close to x, and points far from Points close to must behave like (x) due continuity, whereas points far from x 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 Ga from Section 3 to give transport for approximating continuous functions.
Theorem 4.3. As in Lemma 4.2 let f: Rd - RR and > 0 be given, and define
M = sup 1f(x)).
fTa(x) = f[=][|]++||] $1+
| $1+8
4t M (2ma2)
= +d+ (22 O(1/va),
r:= vd+ In
Let Ga denote Gaussian with the preceding variance a², and let Tr denote the trancated Fourier map constructed in Lemma 3.3 for fig * Goo with preceding truncation choice r. Then
-(1
Vd
5(d+1)
Vd w (8)
4
sup =6
[lf I1..,
Ex (Tr(2),, {2:; x) s (8)
sup |
This completes all the pieces needed prove Theorem
1.5
Proof of Theorem 1.5 Let be given, and let denote the transport mapping provided by Theo- rem 4.3 for fiā * G.. whose various parameters match those in the statement of Theorem [.5 The proof is completed by plugging T, into Theorem 2.1 and simplifying by noting that e 2 w by
definition, and [|s|[ ((M) since 8 1.
8

---

Published as a conference paper at ICLR 2020
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.5and and Lemma 4.2 that threshold and ReLU
networks are universal approximators, with 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 by for further development and references.
Definition 4.4, A sample from a signed (Lebesgue) density p. IRd+1 + R with |P|| L. < 00 is a pair (1) where vi is sampled from the probability density lol/IIp la and sgn(p( i )). Let Ep denote
the corresponding expectation over (ω, s)
This notion of signed sampling also has corresponding Maurey lemma, and analogue for the uniform norm; both are provided in Appendix [ The full detailed universal approximation theorems for threshold and ReLU networks are provided in Appendix E. 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 multiplicative factor vd larger than the (P) bound in Theorem E.1
Theorem 4.5 (Simplification of Theorem
E.
Let f RRd + R and 5 > 0 be given, and define
8
== sup
[f(x)),
f1a(2) := f() [[=] s 1+ 8],
a: vd+ + 2 In (ln(2M/w5(0)
||
Then there exist E I and p: gd+1 R with
2nd
ld| S M + Ilfillle, (2Ta2))/22 and
lplle, S $21sfollen (2Tra2)
so that, with probability 2 1 - 317 over ((s), úz 11 drawn (cf. Definition 4.4
|p lr
m
S 2w) + 1lll [VddI((m) + vn(1/n)
sup f(x) - Ca | |
+
Σ j=1
8j0 )
m
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 [xx = ( p(w) ((1, a)) dw for some density yt as in the proof of Lemma 3.2 introducing the term (C()) gives f(x)
p (' .)) dG))), which is now in the desired form, however the ratio term be large (and truncation is needed to make it finite in Lemma B.2). The refined construction in Lemma 3.3 achieved a better bound on sup [[xi] by being careful about the scaling of the Gaussian, and then standardizing it with a change-of-variabe transformation, but still it yields a random feature transport.
p(m)
Another approach would be to start from the second construction in Lemma 3.1 which writes f(z) If p( ()) (( (w., ž)) dı f p((1) (())(( (wi, .)) a'((i, R)). and thus build transport around i + pl ( w which now uses all coordinates. This transport mapping is still just rescaling, however, and does not lead to improvements when plugged into the other parts of this work.
Consider the following approach to building general T and an associated Reproducing Kernel Hilbert Space (RKHS). To start, define inner product ( and norm || || via || (T, (T,ThH = [1] dG = ||T (G) to justify this Hilbert space, note that it gives rise to the usual kernel product (Cho & Saul 2009), namely
(d(x;; -), (1'): and moreover our earlier predictors can be written as Ea (T(w), ((;; w)) (T, (T,((x;))) ))x
(x,x²) + E. Tb (z: u) T w)

---

Published as a conference paper at ICLR 2020
The utility of these definitions is highlighted in the following bounds; specifically, while given T may have sup,, [[ (T())) 2|2 = oc, truncation can make this quantity finite (and thus Theorem 2.1 may be applied), and the approximation enror can be bounded with |T
Proposition 5.1. 1. The output-truneated transport TB(#) ((w) [[T(2)]22 - B) has
approximation error
IT
sup |=
(TB, ((;:))) (T, S
B²
2. The input-truncated transport T,((O)= == [ s error
with >
vd has approximation
IT|
Tr, ((:: )) (T, ((: ))
sup |
elr-va)a/4
Unfortunately, this formalism can not be applied to the pre- pre-truncation mapping Too from Lemma 3.3 since T 11 = co. Consequently, this approach left as an interesting direction for future work.
OPEN PROBLEMS
The main open question is: how much can the rates 1/420 for ReLU networks and 1/6104 for their NTK be tightened, and there genuine gap? Expanding this inquiry, firstly there three relevant choices regarding which layers are trained: training just the output layer as with random features (Bach 2017b ab. training just the input layer (as in this work), and training both layers. Secondly, for each of these choices, there is question of norm; e.g., by requiring the maximum over node weight Euclidean norms between these settings? Which settings are most relevant empirically? What happens beyond the NTK (Allen-Zhu Li 2019
small, the NTK regime is enforced. Are there genuine separations
Another direction is to use the Fourier tools of Section 2 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 merely polynomial dependence 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., (H 3 y in (Arora al. 2.19)). Perhaps such quamtities can be replaced with a function space or other approximation theoretic perspective on the conditional mean function (and samples thereof)?
Lastly, what are connections optimal transport? It seems natural to choose T transport, in which case one would hope the parameter B == sup,, [|T can be small, and moreover easily bounded the optimal transport cost, ideally in ways similarly easy to the bounding by the Hilbert norm in Proposition 5.1
optimal
ACKNOWLEDGEMENTS
The authors are grateful for support from the NSF under grant IIS-1750051, and from NVIDIA via GPU grant.
REFERENCES
Zeyuan Allen-Zhi and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? 2019. arxiv: 905. 10337 [cs LG].
Zeyuan Allen-Zhu Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. arXiv e-prints, art. 1rxiv:1811 111.:1811.00911.. 004918, Nov 2018.
Zeyuan Allen-Zhie Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. 2018. a -xiv:1811 03962 [cs. I.G].
10

---

Published as a conference paper at ICLR 2020
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. arXiv e-prints, art. arXiv: 005544, Jan 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. 2019.
arXiv: 08584 (es.LG)
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017a
Francis R. Bach, the equivalence between kernel quadrature rules and random feature expansions. J. Mach. Learn. Res., 18:21:1-21:33 2017b.
Andrew R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information Theory, 39(3):930-99) May 1993.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In NeurlPS, 2019.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In NeurIPS, 2019.
Yuan Cao and Quanquan Gu. Generalization Error Bounds of Gradient Descent for Learning Oveer-arameterizzed Deep ReLU Networks. 2019, arXiv: 902. 01384 [Cs.LG]
Lenaic Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Over- parameterized Models using Optimal Transport. art.
arxiv: 1005: 09545
[CS.LG].
Lenaic Chizat and Francis Bach, A Note Lazy Training in Supervised Differentiable Programming. arXiv: 1812:.:111.... .1112.7799 07956795 [math.ock 2019.
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In NIPS, 2009.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. 2018, ArXiv:1811 03804 [cs. LG].
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. 2018. arXiv: 02054
[cs .G).
Gerald B. Folland. Real analysis: modern techniques and their applications. Wiley Interscience, edition, 1999.
Ken-ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural Networks, 2(3):183-192, 1989.
Leonid Gurvits and Pascal Koiran. Approximation and learning of convex superpositions. In Paul Vitányi (ed.), Computational Learning Theory, pp. 222-236. Springer, 1995.
K. Homiik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 2(5):359 -66,, July 1989.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernll:
Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993.
11

---

Published as a conference paper at ICLR 2020
Yuanzhi Li and Yingyu Liang. Learning overparameterizee neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, pp. 1157-8166, 2018.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-Layers Neural Networks. art. arXiv: 18XY::1804.0661,, 2018. arXiv: 1804. 06561 [cs.IG].
Hrushikesh N Mhaskar and Charles A Micchelli. Approximation by superposition of sigmoidal and radial basis functions. Advances in Applied mathematics, 13(3):350-31) 1992.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. 2019. a r vx 910. 01 635v1 [cs. L.).
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparametterizaton:: global conver- gence guarantees for training shallow neural networks. 2019. arXiv:1902. 04674 [cs.LG],
Gilles Pisier. Remarques (dit), pp. 1-12, 1980.
résultat publié de b. maurey. Séminaire Analyse fonctionnelle
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In NIPS, pp. 1177-1184. 2008.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Yitong Sun, Anna Gilbert, and Ambuj Tewari. On the approximation properties of random relu features. arXiv preprint arXiv:1810 04374 [cs LG], 2018.
Martin J. Wainwright. UC Berkeley Statistics 210B, Lecture Notes: Basic tail and concentration bounds, Jan 2015. URL httt:::t////w// stat www.e wttpe///e....eeaooaaa////ttttaaa
Karl Weierstrass. Über die analytische darstellbarkeit sogenannter willkürlicher functionen einer reellen veränderlichen. Sirzungsberichte der Akademie zu Berlin, pp. 633 333-639, 789-805, 1885,
Holger Wendland. Scattered Data Approximation. Cambridge Monographs on Applied and Compu- tational Mathematics. Cambridge University Press, 2004.
Dmitry Yarotsky.
Error bounds for approximations with deep relu networks. 2016.
arXiv:1610. 01145 [cs. LG].
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv:1611 03530 [cs.LG], 2016.
A TECHNICAL LEMMAS
Gaussian Concentration. tion needed throughout.
The following lemma collects a few properties of Gaussian concentra-
Lemma A.1. Let w ~ Ga be a standard Gaussian in Rd, and letr 2 vd be given.
1. / | s Vd.
2. P|[lW|| > >]] S exp(-(r va)² /2); alternatively, with probability least - 17, ||w|| s Vd 2lnn(//n)
3.
||| dG(ww S 2) (-r--ay) S 22(V exp vdj2/4).
hpllsr
4.
/wllrr || [ww]2dG(w) $ 2(r + 2)² exp (-(r-vaj2))
2(Vd
7) exp (-(r- V/)214)
12

---

Published as a conference paper at ICLR 2020
The more convenient form of some of the inequalities will need to following technical lemma.
Lemma A.2. Given b 2 0 and 0 and 2 0 with b 2 2c and then
(x + axaa)eppp((- - -x s (a (a+bb exp((xx - b)* ((c)),
and if moreover a + + 4c,
(x a)² exp( (- 6)3//) (a+ exp(-(x ())(((2)))
Proof. Since In(x + a) N In(b a) + (x (x-b)/(b+))
(x + a)+ b)) /c) < (a (x- // b)/(b/ a))
s (a+b) exp(- //c (x- (26))
< (a + b) exp(-(xr (2))))
Similarly, multiplying the preceding Taylor expansion by 2,
(x + exp(-(( - -x))/c))))))))
(a + b)2 exp(-(x /)2/ct 2(x b)/(b+ (a b) exp(<<xs 6)3/c /c + 2(x 6) /4c))
(a b)2 exp(-(x b)² (2c)).
/ | <
/IIw| = vd.
Proof of Lemma A.7
1. By Jensen's inequality,
2. The claim follows from Gaussian concentration with Lipschitz mappings (Wainwright 2015 Theorem 2.4), specifically since w - || is 1-Lipschitz, meaning
|w||
[||| $1| w'll.
and since E ||
Vd.
3. Note that
{ Twller dG(w) < Σ /
(++i+1) 1)
i=0 [+
whereas the Gaussian concentration from the preceding part grants
P P[| br+df < (xppp(r--i-v//// -i--v)3/2)) exp(-(r vaj² exp(- -1212),
whereby
||w/| dG(w) S (r (1+
dG(w)+ H
dG(w)
||
1=0
$ +
+
i eexp ((r v2)2/2) exp()
1=0
(op(-(r-va)111)
r 1+
> 1=0
expp (exp(-i//2)
Sexp(-(r
v2) (osp-(r-Vad)/2]1 [r 2
The final inequality follows by applying Lemma A.2
with (a, (a,b,c, (,,)) =(3, vd,2,r)
13

---

Published as a conference paper at ICLR 2020
4. Proceeding similarly,
| dG(ww
Σ k=0 (tii|bu||stitt
/
(r+i+ 1)2 dG(w),
bwllrr
s 2(r + 1)²
dG(w)+ + Σ
12
dG(w)
/
i=0
2 1)² exp(-(r -xp(-(r-Vd)(2)) +
1e exp( ((r vd)2 exp(-
1=0
S 22exp(-(r-va)) (r (r+1)²+ +
2 (ip(-i//2)
==0
s 22exp(-(r vd)² Ir 2)²
The final inequality follows by applying Lemma A.2 with (a, (,,,,,,)) (7, rd,
Fourier transforms.
The convention for the Fourier transform used here is
f(w)) = f (x) exp(2rriu' x)) dæ;
see for instance (Folland, 1999, Section 8.8) for a discussion other conventions, and the resulting tradeoffs. Note also the polar decomposition notation f(w) = If(w)) exp(2ri0,(w)) with (0y(w) s The following lemma collects few properties used throughout.
Lemma A.3.
1. 1 I
2. f * = fg and ge S 11)
3. Let a > O be given and define o == (2Ta) Then (Gal Ga (meaning G2 has no radial component, thus 0g. (w) = 0), and
Ga(w) 2/2 = ((())) = (2))
Proof.
1. Directly,
[(w)] / [hx*)] cexp(2rim' x) dx < |
2. The first equality is standard (Folland 1999 Theorem 8.22c), and the inequality combines it with the preceding bound.
3. The form of Ga 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 Go.
ReLU representation. Lastly, the exact ReLU representation constructions (e.g., Lemma 3.1 will use the following folklore lemma to write univariate twice continuously differentiable function as an infinite width ReLU network.
Lemma A.4. Let f + TR. be given with f(0) = f0) and f" continuous. For any 2
/
00
f(z)
a - b) ( (b) db.
ju
14

---

Published as a conference paper at ICLR 2020
Proof. Using integration by parts,
1 o(z (b)
x
8² ' (2)
2 .(" (b) db f/ (f)
2f) (DF(0)6 - -16 f(())bb
=f) =f (=f 0 -())++(00)))
f(2).
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 proof of Lemma 2.5 which here is combined with an application of McDiarmid's is inequality give high probability guarantee.
Proof of Lemma 2.5
Following the usual Maurey scheme
Pisier 1980
E (0y
f
gj
E (1y)
Σ (f 9j)
m
L2(P)
L2(P)
El1 f
93 1 (1_)(P))
E
m
(0g)
1 ElI
91 (P))
m on
1
(191ll - 1l(()(.pp))
= m
E
1
< E., 11 (P((P)
m
< supl g( [ || L.(P))
1
The high probability bound will follow from McDiarmid's inequality. To establish the bounded differences property, define
F(V)= = F( Um)) f 1 Σ Σ)(eo)
La(P)
and note from the general metric space inequality ||l|| - - S 1p all that for any V
(U1,... 2m) and V (u's..., v//)) differing only on single uk # 2/4
(P(V-=(1V)
<
m Σ g(:r) 1
Eo(s
m
(2(PP)
|1((;vz) - g(: ((sin(/)lla
1
m 2 + (bll:1)))l)0))))
2
sup [ 12ace:
veV
15

---

Published as a conference paper at ICLR 2020
Thus, with probability at least 17. McDiarmid's inequality grants,
F(V) S FvF(V) + sup (l((=))) 2ln(1/n)
eEV
and the statement follows by Jensen's 's inequality, specifically Fv)(V) S VVV
Maurey's 's lemma also applies to sampling from signed densities in the sense of Defimition 4.4
Lemma B.1. Let f(x)) = (())g(( (w. 3)) du be given with llPl < oc and is supported on ball of radius B, and let ((sj; Wy ())))== be sampled from p as in Definition 4.4 and define g)(x) g((ū,,)) With probability at least 13.
|pll. L f
m Σ 8,9, j=1
1 22
S sup
m
|
m
LP(P)
Proof. Since
J p(())(((w, 2)) db lppllz, / sgn(p)
[p(W]] |pl|
( z)) du ||l|zz sg((1, i)),
8,08
the sampling procedure indeed provides unbiased estimate of the integral, and thus by Maurey's Lemma (cf. Lemma 2.5 with probability at
least 1 17,
|pll L1
m
Σ f=1
= Iell 00000)((001))))
8j91
m
m j=1
LP(P)
LP(P)
1 + / (n((n))
sup s ||ele
||sg( (w, (1)
sE(11) |
v m
1+ (n/nn)
Illle |
sup
(llex(P)
m
Lastly, here uniform norm analog of the preceding L2(P) signed density sampling bound. Interestingly, the bound only gives a vd degradation with o', and degradation for a. 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 T995 Sun et al. 2018). The proof somewhat more complicated than the proof of the Maurey lemma, and in particular needs to be bit more attentive to the fine-grained structure of the functions being sampled.
Lemma B.2. Let density p: Rd+1 RR with ||p|l, < oc, and let ((8j, (1),W;))) ())) be a sample from p in the sense of Definition 4.4
1. With probability at least
2n,
/ ((1))'(((ū,))) [ 11
((ū,5)) F)) dū |lell. Σ ( i))
[8(d+ vin(1/m)
sup
5
vm
2. Suppose p is supported on the set W {w Rd+11 probability at least 1 2n,
||M|| S r, |6|
S ||]]]
With
4rllpliz mm
sup |=
((1)) F)) dı
(
<
I VIn(L/m)
16

---

Published as a conference paper at ICLR 2020
Proof of Lemma B.2
In both cases, letting g denote either of o' or o,
/ p(aa)a((00 8)) dú
Illll
Σ S
sup || 1
m
= =Ilelle
sup |
E (w, i)) die
m Σ و
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; (unn et al., (018)). Continuing, with probability at least 2y,, standard Rademacher complexity (Shalev-Swwartz & Ben-David 2014) grants
1 S5 [))
s 2Rad (()))((()))))) |||||| = $1})
sup E Dggg((e) ((w, 2)) du ||
m E
In(1/n) 2m
+ 3 sup (9( 2))ly NeW
||
where W is a constraint set on á (when g = o', it is Rd+11 whereas with g = a is |b| S ||||| r)) To simplify further, note that Rademacher random vector (c1,.... (.n) is distributionally equivalent to (s1é1,... Em) for any fixed vector of signs (S1...., 8m), and therefore
Rad (((000((1)) ;>))>>>>>> ||س|| s s1})
E. sup Σ (53g)((0,)))
||
E. sup
Σ {))((ūūā))
|| 7
Rad {()(( : |||||||||| s1})
Combining these steps, with probability at least - 2n,
llPll. E5)(((2)).0))
(( B)) 8)) dw
sup ||
2Rad ((o((15;)))) |||||| S <1}
In(1/v) 2m
$ Slplle,
+ sup 19((1, (o((),,))) new
The proof now splits into two cases E fo'.a), bounding the remaining terms.
1. Since the range of o' is {0, 1}.
sup
(1 < 1,
nEW |
and the Rademacher complexity is the VC dimension of linear predictors, thus
Rad (110((1),)))) +))(,, ||-||| s 11) S 2(d 1) In(m + 1)
m
2. In the case g o, since W (w E Rd+1 || S r. [b] - ||0 17,
sup (o((0,))) < sup
Iw + bl < 2r.
sew
S| b bislll ||
æ <1
17

---

Published as a conference paper at ICLR 2020
Moreover, the Rademacher complexity is standard combination of the Lipschitz composi- tion rule and linear prediction rules (Shalev-Shwand Shwartz Ben-David 2014). and thus
Rad (()))())))))) ||||| s <1}) s Rad ((((,))))) : ||||| S s1})
4r
Vm
C DEFERRED PROOFS FROM SECTION 2
For convenience throughout this appendix, define
B = sup [[]
and
B. = sup 6..8
[T, s)]12 - Emm
+ R.
The first step is to prove eq. 2.2 restated here follows. Lemma C.1. With probability at least 17 over (W, S),
Σ 0,)) EE (T(w), ((;
I EB 1/2+2/in11//)
(2(P)
Proof. The proof proceeds by applying Maurey sampling (ef. Lemma 2.5 the functions gj g,(x) m (Tz, (x())) noting by Lemma 2.4 that
f(x)
93
(z)
E W.s
Σ
(T),
(T. S), (2 (.. W.S) .)) (T(w), (xx; w))
W.s
Applying Lemma
2.5
with probability least 17.
m
supai. mll (Te(w, s), le v. 8)) [x2(P))
1+ 22
9j
171
m
j=1
12(P)
where
262
sup 6,s
(T) (, 8)) (P))(P) sup
TT(() p. ú, s)(12
12,8
m
Next, the restatement of eq. 2.3) is as follows.
Lemma C.2. With probability least n, If
Vd vd+ 2
In
Evmmx Bv2
)
then with probability at
least 1 - 1}
Σ ()))))))) Σ
syc Vm ((T,,)))
< B.B m/T
+ eB.
L2(P)
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 idealized TV which does not truncate, whereby
(T(w), (w0 #) (2i1, 8)
B |
1-
c/m
m
18

---

Published as a conference paper at ICLR 2020
The event |gnn( ( m)) # sga(( (T)) implies the event [] (2, ii) I Bllöl//e/m] and thus,
additionally using rotational invariance of the Gaussian,
E - of
- P sgn (1ē, x)) + sgn (T (w)) x3))
< P
[| (ū,, ()
/
[1m1]
|| - /l
B/(r/m)
E --2²/2
dz
2
-B/(evm)
B
6
mm
Returning to the general case with truncation, by Lemma
A. 1
using the assumed lower bound on R.
B
i|lli| > R| S exp( vd)²
vd)²
which gives the final bound via triangle inequality.
With Lemma 2.6 in hand, the proof of Lemma C.2 is now 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
((T.(1))))) (T)(()..),))) and f(x) E g(;; s)
g(x; 0. == m (Te (T(( s), Pe(2; w. 8))
vm"
well (x) g(2; úyy, sz). Using this notation, the goal of this proof is upper bound
Σ ()))))))
Σ o ((T),))
SjC
Σ 91
=
LP(P)
Lz(P)
By Lemma 2.5 with probability at least
Σ gj
$ [Ifllzz(P) +
1 ΣΦ 9j m j
m
j
L2(P)
L2(P)
(n(nn
< ||ll + sup ||o(; w. 8) (2(
Vm
To control these terms, fixing any (w, s), holds by positive homogeneity of a that
|
[| w. ))l = =m² E. Tc(ū,)), s). & (x;
vm कt TT(
S m B² E
S 2m B?
On the other hand, by Lemma 2.6 for any |||||| 1
[s(x)) < En,
To(ū, Th $,
o (2; To T.(ū,)))
mm
[||ā|llo((T
-
< B.E,,
< eB.
B
Vm
E
which also upper bounds [|]])
19

---

Published as a conference paper at ICLR 2020
The proof of Theorem 2.1 now follows by combining Lemmas C.1 and C.2
Proof of Theorem
2.7 By Lemma A.1 and union bound on (wi, wmn, max, ||
R, thus
[T
B
max [T, ااyl < max
I
evm
EVm
Moreover, R Vd vd+ 2 In
svmu Bv2
and thus the two other bounds from Lemmas C.I and C.2
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. The first steps the same for and o', and indeed match the initial steps of
Barron 1993). namely
(w) S(0) Re
exp(2nin' w) f(r dw eexp(2rii w + (w))) dw
Re
/ cos (2T(z' w + (w())) (f(w) dw.
For convenience, define h(2) == cos (2 whereby
f(x) f(0) Mxx" ww + (f(w))
dw,
(D.1)
and the proofs not differ for both activations and from
Barron 1993
1. Consider first o'. Since ||>:|| < 1, by Cauchy-Schwarz it suffices to approximate h along the interval [- || (w) [m]] 0y(w]] By the fundamental theorem of calculus,
((w,.) ()(w)) h (- |l||| (w)))
(0,
b((b) db
|w]l+8f(w)
M M(b) + (w) bb 2 -||w|| (w)) db
(w()(ww)- - -b)1(=' + 0 | 2 6] db,
b b (
/ (((0(ww)- -)1(==' w +
0 [ [b|] db,
where the last step follows since 1 w + b 2 0] implies 2 -||w]. Plugging this back in to eq. (D.I) and still using h(z) = coss(2m.))
[()) - ((0) / [f(we) cos (2 w + 0y(w)) dw
/ -(((w))) (((w)))
| |M(IIlu]|+ + / (((0(w)) D) +bb+ +b> []][| 2 [b]] db dw,
20

---

Published as a conference paper at ICLR 2020
which after pushing more terms onto the left hand side gives
(())-((0) - / ( || dw
=- -/ [(w)))((0)())) b) [|][| > [b]] db
2T / [(((w] sin (2 6))o ((0o, 3)) 2 [6]] deū,
which gives Fso f for | S 1. To bound the error of Fr. note by the form of F for any |||||| I that
[sxx] - F.(x)) = 2TT /
([(w))
(in))(())( - b))o ((0, [ [[ww 2 [b]] db dw
/ellsr
|wl >r / M wl
S 2
(in))](sn(227( - b)) o ((ū, 2)) db dw
S 2x S |vl >r
|f(w)]
dbdw
4x
||wl|
[f()w) dw.
|ml >r
2. Now consider Rather than using FTC as above, this proof replaces h with ReLUs via Lemma A.4 which requires function which is both zero and flat at O. To this end, define
H(b) = li(b + q) (h(g) + (4) with q = -|wl|| + 0f(w))
whereby H()) = 0 = H')). Invoking Lemma A.4 on H gives, for any 2 == w²x x
()(w)= 29. 9.
M(2) - (h(2) + (2 - ())(
H(= 4)
= / H" (b)0(((2- b) 2 0l
/ H" H" (b))(ww" + + + ||||| - (w) - b)n 2 Oldb
/ -[[[ [|| =6 db
b ||m|| b
/
[6|] db,
the final equality since -b || implies w + < |w|| + < 0. thus ( 0 and this case has no effect. Plugging this back into eq. D.I.
f(x) - s(0) / [f(we) M(2)) dw
/ If(w))
h(g) + (=- ()-)) - -/ H H"[[ ()) 2 [b]] db dw
-/ -f1((e)) ((oo)
((() + (w +wo's+lw|\) - H"([|]]| b) a) [|]] 2 |b|] db dw,
21

---

Published as a conference paper at ICLR 2020
which gives Q any ||>||| $
for ||||| S 1 after expanding h and H. To bound the enror of Qr, for
/ 100 |>r
If(w)] / 11 6))("' ()){(()) > |6]] d6 dw
- Qx)
1 /Iwllr (((o)) / [A (ol B)) [[]]] 2 bi] db
$ 4m² { 1w 1ar
[f(w))
aw i) du
-|ll
$ 4m [
||ill
[f(w))
-[lloll (112ol) + (6]) cbb dw
1w 1ar
< 12
||0||22 ([w) dw.
||ll|2r
Next, Lemma 3.2
converts Lemma 3.1 into (random feature) transport map by introducing the
fraction G(#)/Gla
Proof of Lemma 3.2 Starting from the construction in Lemma 3.1 again using h(2) cos (2TT2) for convenience, and manually introducing a factor G(Ø),
f(x) - - - / ((w)))(()({))) || dw
// ((w))) b)1 w + [] > [b]] db
/
f(w)] ('(0((w) G(
(aoou)))-(o(((() b)o ((0, [6]] dG
To construct Too, rotational invariance of the Gaussian gives E. [ 2 1/2, thus
f(0)+ f ((w)) dw = / f(0) + / [f(w)))(()(()) || du d'((", 2)) dG((w,
and transport mapping is (w,, (0, Rdd x R with
lf(w) G(ū)
Poo (w) 2 [(0) [f(())((0)())) [ell By construction, E7 (w) 0( x) F, (z). and therefore Lemma
n (((0(ww) [[][[] 2 [b]],
grants for all
||^>||| S
f(x) = E, (Tx) ((; and |(()) - E (T((O), (c:; w)) s 4m /
[f(w)l-I[o|) du.
With more care (in particular, crucial change of variable), much better bound is possible for convolutions with Gaussians.
Proof of Lemma 3.3 By Lemma A.3 setting = (2
Ifa (w) = If (w) (G = (2 (2)))//(((
Plugging this into Lemma 3.1 and again defining (a(2) == cos(2 for convenience, but unlike
Lemma 3.2 performing change of variable to directly introduce G(w)), and then manually introducing
22

---

Published as a conference paper at ICLR 2020
G(b),
- Sa(0) / (fala(a)))(00 - l|
(lw)) du
- /| (100))00000000000000000000011111 [6] dbdd
(1o
(2x) // -
2 [b]] db
-22702)0/20 (( 6)0'(0 [ d|b|] db dw
=2 (d+ / (1()) (dw) - b)o ( ((ū, 2) 1 wlll > |6]] dG
As in Lemma 3.2 the transport is constructed by using ((ū = 1/2 to model constants:
(, 6) (O..... 0, (w)r, where
(,)) = 2 [a(0) + (a(()))(00,.00 -[10l)) du
||m|| S r (2md3)(a+1))) 1)/2 (((w))) /22h (dww) b)n [
with f(x) Eg (z), (z:; w)) for ||^||| s 1 by construction.
When 0G, by construction
sup [TT( < (0) + 2 / [fa(v)) 2T (2mo))))
[f(dn)) e
sup h |
where [f(ww) when fa Ga (meaning f itself is the Dirac at 0), and more generally Lemma A.3 grants [f(ww)] < ( as in the lemma statement, these cases are summarized with [ < My. Plugging this in and simplifying further via Lemma A.3
sup sup (T) 2 / [(x))G(-x)) da 2/2 / [(())((m/))) du 2 2mx 2 (d+1)/2 M,
sup 2/2
[b|šr
2 2 M + 2(2m 4/2
sup /2/2 bi
For the approximation estimate, for any ||>||| S 1, the preceding derivation and Lemma A.1 grant
[(x) ((z;
= E (To (w) ((x; w))
22T 2
1wllir /B1/T (f(dw)) sin ( + 0r (w)))o'(W" 2)) db dG(w)
2mm 3/
dbdG(w)
S <mm(2 (4433//3M { [[w])dG((w)
||/||Srr
< 4412 (-orp-((--v/e- VV1j2/4)
E DEFERRED PROOFS FROM SECTION
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, for nearby points, the other for distant points.
23

---

Published as a conference paper at ICLR 2020
Proof of Lemma 4.2
Splitting the integral into two terms, for any || s 1,
/ (o()))a(=)dz / Go(()) -2) =)
((x) (/is Go)
/ [1(())G (z) / /1(oo=))Go(2ddd
=))x(2)
/ /sadoo - A5(x z) Ga(z)dz
S |HISS (1((0) - f1(2 2) Ga(z)
$ A ((a(2) flo(1 2) Ga(z)
Analyzing these terms separately, the definition of Wy (6) gives
JiSISo (((()) ( flz(2 - =) Ga(z) |1
wr(o)Ga(<)dx wo()),
whereas Gaussian concentration (cf. Lemma A.I gives
Jielso [ia(z) fis(2 2)) G= s 2M P || s 2M exp(- exp(((6/a-va)//) s wy(
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 || < 1.
f(x) EE (T,(()
1 (z; x))
< 4n (2m ( (d+1)) M (Vd exp (-(r- vdd2/4) (o))
Moreover, plugging into the estimate on sup
[T, provided by Lemma 3.3 gives
sup [T) 2 M + (2 d/2 (2
(1+ 2 22
where Lemma A.3 and the choice of give
e2 S ceelr-vas
and
where
=0 )
(r=va)²
w6(
and noting moreover that ((5/Va).
To close this section comes the full version of Theorem 4.5
which gives explicit constructions for both threshold o' and ReLU a. Interestingly, in the case of a', it is not necessary to truncate the density, as the case everywhere else in this work.
Theorem E.1. As in Lemma 4.2 let f Rd and 5 be given, and define
5
M = sup [f()),, ||
= (o(=)== s 5].
Vd+ (2n((MM/s((0)
Let Ga denote a Gaussian with the preceding variance a², and define h f/g Go with Fourier transform satisfying radial decomposition h(w) [h(w) exp(2Tii, (w). Lastly, let P be a probability measure supported || < 1.
24

---

Published as a conference paper at ICLR 2020
1. Additionally define
6 :1 :===(0)+ / [[(w)] (2m(0n(w) [| dw,
pi == 2x[h(w)) () b))1 [1b] - ||x=|]]
Then
2nd
lei S M + [ijsllz, 22/22)
and
||Iile. s 211 Ls (2tra2)d+1*
and with probability at least 1 3n over a draw of ((s,, úF)); from p1 (cf. Definition 4.4
1 / 2lm(1/n)
f
Ci + |pPll Σ
s50
((ū)s))
$ 2wv + |pillz
f=1
L2(P)
sup |
f(x)
01 + Pplll Σ
m
5 (
(w) + IpIle,
[vs(a+ + 1)lmmmm)mmm++ 1) + vin(1/))
vm
2. Additionally define
c2 f(0)f(0) / |i(we)] (2os(22(00(1)))) (|ll))) / |||| (0n(2 [| dw,
02 = / w w/((w))dw)
vd + 2/ In
w7( (2( = 4x. (h)) cos (1( b)) s ||ll| S r2),
and for convenience create fake (weight, bias, sign) triples
(w, b, m) = (0, 102, m- sgn(c2)), (w, b, s) = (az, 0, +m),
(w, (), == (-az, 0, -m).
Then
||a2|12 S vdl fll d(2xa²)-a/2
(2T))dd
[pelle, s 21liiille, V (2ma²)d+11
102| $ M 2l Il,, (2Taa)-aa7?
and with probability at least - 34 over a draw of ((8j, úū mz from p2 (ef. Definition 4.4)
m m-+3
1 2ln(1/n)
f
5jol
$ (w) + r2llplla
mm
1=1
L2(P)
m m
(0 4r2lle1la
sup
[(x)
( -))
[ v vln(1/n)
vm
Proof.
1. By Lemma 3.1 and the choice of b1, for any || <
1(x) c1 + / p1())o'((11) dw,
25

---

Published as a conference paper at ICLR 2020
thus by Lemma 4.2 and Lemma B.1. defining hy 1 (((ū))))) )) for convenience, with probability at least
s (cI + " k//mm)
I11 h 1ll2z(1) + 11 (ci + Ehy/mi
Lx(P)
La(P)
1+ 2 (m(1nn)
- 2wr( + -1lpillz,
sup ||
I (lan(P)
m
v 2lm(1/n)
S 22n + l|pilla,
mm
Similarly, the uniform norm bound follows by Lemma 4.2 and Lemma B.2 with probability at least 2n, for any | 1,
((x) - (ar + Ens(t)/m) s1f(x) Max) + m(xx) (c1 + Σns(o)/mg)
S 2w, + ||pilla,
[V8(d + 1) In( + 1) + vln(1/n)
vm
For the estimates on |ci| and ||pi ll.. note setting = (2TT) -1 note by Lemma A.3 and change of variable w + oo and Lemma A. that
|pIlIe s 2 / Iis Ga(w)) [ s || db
4T11sille / (2T))(2 Go()) dw
= 4n 4/2 (1 / (oovoll dw
(2m) 4/2 1 fisisll, / [ dw
4 (2 4/2 d 1.
2nd
s 211fiallzn (2ma²)d+tI
Similarly,
lall S M + [1l / (a) S M + [[sille, (2m02)a/2
2. By Lemma 3.1 and Lemma A.l and the various chosen parameters, for any |||||| S 1.
b2 + (r, (2) + p2(1)) x)) dō h(x))
< 12m²
| | (1 (w:) dw
w/ >>2
< 24m² (v 7)2 exp(-(r2- -x2
$ (o)
Thus by Lemma 4.2 and Lemma B.1 defining hy = || L, 8 ( (ıū,, .)) for convenience, with probability least 1 77.
n+3
h m
<IIʃ Allea(P) +||s - (b2 + (.) + Epp k +
Ryp 81h
Σ
8 hi m
Lz(P)
5
Lz(P)
1 2 In (1n)
< 3w (6) ||p2|la, |
sup (1o((W; (I)x(P)
v m
+ v In(1/n)
$ (3w 2r211plle
/
26

---

Published as a conference paper at ICLR 2020
Similarly, the uniform norm bound follows by Lemma 4.2 and Lemma B.2 with probability at least 21j, for any ||>| $ 1.
m+3 ((x) Σ 1=1
hm(z)/m
<|5(2) - M()) +1 - (b2 + x'02 + s1.s1/1( (x) + E
s1 (x) - syhy(r)/m
P2
4r211p2 La
+ In(1/n)
vm
For the estimates on |ci| and ||d |l.., note setting @ == (2Ta) -1, note by Lemma A.3 and change of variable w + obw and Lemma that
122ll1, S 4x² / ( / 1[66] - ||w|| S r2l dbdw
I 8 88. / /wwliss (2 Gd (p(w)) dw
=2x²(2x) 4/2 1.1ollz / IIouitsr
1 G(w) dw
s 8x (2x) dd+1 Iffalle, f
[[=]]G[()) dw
< dd (2 1/2 0 111isle.
(2
(2ma2)dt1
Similarly,
cc2l s M + |ffille,, / + ([wl))a(()) dw
S M + (2m / (1 + (k dG(w)
$ M + 22 11 (2
||a2|22 = || w k(w)) dw
I I ||w|| ([]]) dw
< [| ll, (2m03)d/2 / (1 (w)) dw
S Villsiolle, (2
F DEFERRED PROOFS FROM SECTION
Lastly, the two short proofs leading to the RKHS bounds.
Proof of Proposition 5.7
1. By Markov's inequality
/ 1[[T(W)]12 > B3 dG
|
7
B
27

---

Published as a conference paper at ICLR 2020
thus by Fauchy-Schwarz, for any |||||| - 1,
|= / (Tb(w)) - - 2o' (()
(TB, ((x; )) (T, (0:(2=)))) x
=
- / 1 [ITT(1))22 122 > B| TT (b) 2 (1t,
< / 1 [ITT(w)]l2 > BJ dG((w) / (T())t) 2 dd(())
11
/
/2TT(T))PdG(())
B
|1
v2
B
2. Proceeding similarly, but now using Lemma
A.1 to control the indicator,
(Tr,, (xx::))) (T, o(2; -)
/ (T. T(ū)) 2o ((w () dG(())
< / 1 [llill2 > +] | (6) क jo'
/ 1 [100ll > r] /ddG(()) / (TTiaaa)' dG(x)
- exp (-0--08//2) / 2
va8212)
17|
e(--V0)/4
28


Reviews:
[{"review_id": "Hyge3AC3FB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies approximation properties (in L2 over some data distribution P) of two-layer ReLU networks in the NTK setting, that is, where weights remain close to initialization and the model behaves like a kernel method given by its linearization around initialization.\n\nThe authors obtain a variety of results in order to obtain such approximation guarantees, which are obtained by sampling from a so-called 'transport mapping', which is essentially a function T:R^{d+1}->R^{d+1} with a bound on sup_w ||T(w)||, which can approximate well various classes of target functions (section 3).\nIn particular, they show that such a sampling leads to weights close to initialization, that the neural network function is close to its linearization in L2(P), and that the linearization is close to the target function in L2(P).\nTogether with a control of the norm of T required to approximate the target function, this leads to approximation bounds in Theorem 1.3.\n\nThe techniques used to obtain transport mappings are quite interesting and seem novel, and the general approach for controlling various steps from neural network function to the target function in L2(P) norm in the NTK setting is insightful and novel as far as I know.\nThat said, the presentation lacks a certain amount of polish in its present form, which makes me lean towards the reject side. I also have some comments related to novelty of certain aspects.\n\nComments:\n* the paper is not well organized, with the main result appearing in the introduction with little details on the involved quantities, no clear separation or connection between intermediate lemmas in later sections, and very little motivation and explanation of some results. Further, there are many typos and inconsistent notations throughout which make the paper hard to read.\n\n* the sampling result in Lemma 2.1 is very similar in flavor to random feature approximation results (for the NTK here), e.g., [1, Proposition 1], which could perhaps be more precise in practice as it is data-dependent, and only needs an L2 control on the function T. Can this be applied here or would the initialization term mess things up? A comparison would be helpful either way.\n\n* the approximation rates should be discussed more (are they optimal?), and compared to prior work, both on general two-layer networks, and kernels arising from a similar setup, in particular in [2] and the cited Sun et al. (note that the NTK behaves similarly in terms of approximation, see [3])\n\n* the section on the \"natural RKHS\" is largely unclear, as is the corresponding bound in Theorem 1.3 (shouldn't B be proportional to the RKHS norm?)\n\n* how these results apply to networks obtained via optimization in the NTK regime should probably be discussed more\n\nsmaller things:\n* eq (1.2): what is the mearning of the epsilon factor? is it standard?\n* p.2 \"to not yield\" -> do not yield\n* \"with scaling... width\": rephrase (and, do you mean dataset size?)\n* \"one 1/m is then pushed\" -> one 1/sqrt(m)?\n* throughout: pick a consistent notation for derivative of relu (sometimes it's sigma', sometimes an indicator)\n* section 2: here it seems like T(w)/(eps sqrt(m)) is just the movement from initialization and T_m,eps(w) are the final weights, while in the introduction T(w) indicates the final weights, this is confusing notation. Also, shouldn't T_m,eps appear in the bounds?\n* section 3: should -> shows?\n* lemma 3.1, 3.2: specify that the other coordinates are 0, also missing dG(w) in the definition of g. What do we lose from the use of truncation?\n* lemma 3.5: sup_x or just L2(P)?\n* section 3.3: H is just L2(G) here? Also, the kernel is not universal with only even terms, but the bias fixes that, see e.g. [2,4].\n\n\n[1] Bach. On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2017)\n[2] Bach. Breaking the Curse of Dimensionality with Convex Neural Networks (2017)\n[3] Bietti and Mairal. On the Inductive Bias of Neural Tangent Kernels (2019)\n[4] Basri et al. The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019)\n\n\n===== update post rebuttal =====\n\nThanks for the detailed response, I am increasing my score as the new version looks much better.\n\nI am a bit puzzled (and surprised) by the gap in the rates between NTK and relu random features, as it seems to suggest that only training second-layer weights while leaving the first layer at random initialization yields better rates than the NTK regime, if I understand correctly? If so, is this due mainly to the linearization step, i.e. Lemma 2.6? It would be good to include some further discussion on this in the paper.\n\nAs per approximation by random features/sampling, note that [1, Prop. 1] only requires a sup control on random features (which is quite trivial here with bounded data), not on the \"transport\" (beta in their statement).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1edMNKV9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).  \nThe 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. \nThe 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. \n\nEvaluation: 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. \n\nMinor comments: \n* 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) \n* 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. \n* I'm not sure \"transport\" is the ideal term -- it brings to mind \"optimal transport\", and I kept expecting some Wasserstein connection. \n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers 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 reviewers agree this content is of general interest to the community and with the proposed revisions there is general agreement that the paper has merits to recommend acceptance.
Decision: Accept (Poster)