Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary: the paper consider representational aspects of neural tangent kernels (NTKs). More precisely, recent literature on overparametrized neural networks has identified NTKs as a way to characterize the behavior of gradient descent on wide neural networks as fitting these types of kernels. This paper focuses on the representational aspect: namely that functions of appropriate "complexity" can be written as an NTK with parameters close to initialization (comparably close to what results on gradient descent get).  
The main technical ingredients are a constructing a "transport" map via a Fourier-expansion style averaging (ala Baron), and subsequently subsampling this average ala Maurey-style analyses to get a finite width average. 
The authors also identify function classes which are well-behaved with respect to these techniques: smoothed functions (via convolving with a Gaussian), functions which have a small RKHS norm (for an appropriate RKHS derived from NTKs), functions with small modulus of continuity. 

Evaluation: the paper is a strong contribution, on a topic which is of great current interest, and I recommend acceptance. It is very nice that many of the standard tools in approximation theory (Fourier expansions, Maurey sampling, etc.) play nicely with NTKs, and also that the scaling of the # of neurons necessary that appears in the current literature can be also recovered via a representation theoretic viewpoint. The paper is written well, and is easy to read. 

Minor comments: 
* I'd rearrange the bullets bounding B_{f,\epsilon} for the various subcases of Theorem 1.3: I think the RKHS is the most "vanilla" bound, given that you can extract a RKHS; bounds in terms of the modulus of continuity should go next (this is the "weakest" assumption); smoothed f's should go last (this is like a smoothed complexity kind of result) 
* w_f isn't defined until section 3.2 -- I'd put a pointer in the statement of Theorem 1.3 to the equation, not just the section. 
* I'm not sure "transport" is the ideal term -- it brings to mind "optimal transport", and I kept expecting some Wasserstein connection. 


review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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).
review_title: Official Blind Review #3

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)