THE COMPARATIVE POWER OF RELU NETWORKS AND POLYNOMIAL KERNELS IN THE PRESENCE OF SPARSE LATENT STRUCTURE
There has been a large amount of interest, both in the past and particularly recently, into the relative advantage of different families of universal function approximators, for instance neural networks, polynomials, rational functions, etc. However, current research has focused almost exclusively on understanding this problem in a worstcase setting: e.g. characterizing the best L 1 or L ∞ approximation in a box (or sometimes, even under an adversarially constructed data distribution.) In this setting many classical tools from approximation theory can be effectively used. However, in typical applications we expect data to be high dimensional, but structured -so, it would only be important to approximate the desired function well on the relevant part of its domain, e.g. a small manifold on which real input data actually lies. Moreover, even within this domain the desired quality of approximation may not be uniform; for instance in classification problems, the approximation needs to be more accurate near the decision boundary. These issues, to the best of our knowledge, have remain unexplored until now. With this in mind, we analyze the performance of neural networks and polynomial kernels in a natural regression setting where the data enjoys sparse latent structure, and the labels depend in a simple way on the latent variables. We give an almost-tight theoretical analysis of the performance of both neural networks and polynomials for this problem, as well as verify our theory with simulations. Our results both involve new (complex-analytic) techniques, which may be of independent interest, and show substantial qualitative differences with what is known in the worst-case setting.
The paper studies the representational power of two-layer ReLU networks and polynomials for approximating a linear generative model for data with sparsity in the latent vector. They show that ReLU networks achieve optimal rate whereas low degree polynomials get a much worse rate.
Overall, the results are strong, the authors provide a lower bound on the degree of polynomial needed to approximate the model indicating the power of non-linearity. The observation of moving away from uniform approximators is well-motivated. The approximation theorem for ReLU is intriguing and uses new ideas which I have not seen before and are potentially useful in other applications. So far, only rational functions have been able to give such approximation guarantees. However, the motivation for studying sparse linear regression from a representation view-point is not very clear. Ideally, you would like to study representation for more complex models. 
Questions/Comments:
- Related work is missing prior work at the intersection of kernel methods and neural networks, please update.
- Define notation before using, for example, \rho_\tau^{⨂m}
- Expand proof sketches, they are not very clear, also full proofs are written with not much detail.
- Is the dependence on \mu tight? The current dependence sort of suggests that you need the observation matrix to be very close to identity.
- Proof of Lemma B.1 is unclear, could you explain how you deduce the lemma from the inequality?