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 worst case setting: e.g. characterizing the best L1 or L_{infty} 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 concept of representational power has been always of great interest in machine learning. In part the reason for this is that classes of "universal approximators" abound -e.g. polynomials, radial bases, rational functions, etc. Some of these were known to mathematicians as early as Bernstein and Lebesgue 1 -yet it is apparent that not all such classes perform well empirically.In recent years, the class of choice is neural networks in tasks as simple as supervised classification, and as complicated as reinforcement learning -inspiring an immense amount of theoretical study.Research has focus on several angles of this question, e.g. comparative power to other classes of functions (Yarotsky, 2017; Safran and Shamir, 2017; BID0 , the role of depth and the importance of architecture (Telgarsky, 2016; Safran and Shamir, 2017; BID6 , and many other topics such as their generalization properties and choice of optimization procedure BID7 Zhang et al., 2017; BID0 .Our results fall in the first category: comparing the relative power of polynomial kernels and ReLU networks -with a significant twist, that makes our results more relevant to real-life settings. The flavor of existing results in this subject is roughly the following: every function in a class C 1 can be approximately represented as a function in a different class C 2 , with some blowup in the size/complexity of the function (e.g. degree, number of nodes, depth). The unsatisfying aspect of such results is the "worst-case" way in which the approximation is measured: typically, one picks a domain coarsely relevant for the approximation (e.g. an interval or a box), and considers the L ∞ , L 2 , L 1 , . . . norm of the difference between the two functions on this domain. In some of the constructions (e.g. BID6 Safran and Shamir, 2017) ), the evaluation is even more adversarial: it's the mean-square error over a specially-designed measure.Instead, in practically relevant settings, it's reasonable to expect that approximating a predictor function well only on some "relevant domain" would suffice, e.g. near the prediction boundary or near a lower-dimensional manifold on which the data lives, as would be the case in settings like images, videos, financial data, etc. A good image classifier need not care about "typical" data points from the ∞ -ball, which mostly look like white noise.The difficulty with the above question is that it's not immediate how to formalize what the "relevant domain" is or how to model the data distribution. We tackle here a particularly simple (but natural) incarnation of this question: namely, when the data distribution has sparse latent structure, and all we ask is to predict a linear function of the latent variables based upon (noisy) observations. The assumption of sparsity is very natural in the context of realistic, high-dimensional data: sparsity under the correct choice of basis is essentially the reason that methods such as lossy image compression work well, and it is also the engine behind the entire field of compressed sensing BID5 . In this paper, we considered the problem of providing representation lower and upper bounds for different classes of universal approximators in a natural statistical setup that exhibits sparse latent structure. We hope this will inspire researchers to move beyond the worst-case setup when considering the representational power of different function classes. Figure 1: Degree vs Log L2 Error on test set for different values of n, the dimensionality of the problem. This plot was generated using a training set of 8000 examples from the generative model and a test set of 1000 additional examples; error is unnormalized.The techniques we develop are interesting in their own right: unlike standard approximation theory setups, we need to design polynomials which may only need to be accurate in certain regions. Conceivably, in classification setups, similar wisdom may be helpful: the approximator needs to only be accurate near the decision boundary.Finally, we conclude with a tantalizing open problem: In general it is possible to obtain non-trivial sparse recovery guarantees for LASSO even when the sparsity k is nearly of the same order as n under assumptions such as RIP. Since LASSO can be computed quickly using iterated soft thresholding (ISTA and FISTA, see Beck and Teboulle (2009)) , we see that sufficiently deep neural networks can compute a near-optimal solution in this setting as well. It would be interesting to determine whether shallower networks and polynomials of degree polylog(n) can achieve a similar guarantees.Ankur Moitra.
Beyond-worst-case analysis of the representational power of  ReLU nets & polynomial kernels  -- in particular in the presence of sparse latent structure.
{"src": "scitldr-AIC_train", "paper_id": "rJgTTjA9tX"}