This paper establishes rates of universal approximation for the shallow neural tangent kernel (NTK): network weights are only allowed microscopic changes from random initialization, which entails that activations are mostly unchanged, and the network is nearly equivalent to its linearization. Concretely, the paper has two main contributions: a generic scheme to approximate functions with the NTK by sampling from transport mappings between the initial weights and their desired values, and the construction of transport mappings via Fourier transforms. Regarding the first contribution, the proof scheme provides another perspective on how the NTK regime arises from rescaling: redundancy in the weights due to resampling allows individual weights to be scaled down. Regarding the second contribution, the most notable transport mapping asserts that roughly 1 /δ 10d nodes are sufficient to approximate continuous functions, where δ depends on the continuity properties of the target function. By contrast, nearly the same proof yields a bound of 1 /δ 2d for shallow ReLU networks; this gap suggests a tantalizing direction for future work, separating shallow ReLU networks and their linearization.
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.
The 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).
In 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).
Together with a control of the norm of T required to approximate the target function, this leads to approximation bounds in Theorem 1.3.
The 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.
That 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.
Comments:
* 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.
* 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.
* 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])
* 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?)
* how these results apply to networks obtained via optimization in the NTK regime should probably be discussed more
smaller things:
* eq (1.2): what is the mearning of the epsilon factor? is it standard?
* p.2 "to not yield" -> do not yield
* "with scaling... width": rephrase (and, do you mean dataset size?)
* "one 1/m is then pushed" -> one 1/sqrt(m)?
* throughout: pick a consistent notation for derivative of relu (sometimes it's sigma', sometimes an indicator)
* 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?
* section 3: should -> shows?
* 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?
* lemma 3.5: sup_x or just L2(P)?
* 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].
[1] Bach. On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2017)
[2] Bach. Breaking the Curse of Dimensionality with Convex Neural Networks (2017)
[3] Bietti and Mairal. On the Inductive Bias of Neural Tangent Kernels (2019)
[4] Basri et al. The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019)
===== update post rebuttal =====
Thanks for the detailed response, I am increasing my score as the new version looks much better.
I 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.
As 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).