Title: THE COMPARATIVE POWER OF RELU NETWORKS AND POLYNOMIAL KERNELS IN THE PRESENCE OF SPARSE LATENT STRUCTURE

Abstract: 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.

1. INTRODUCTION:

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; Telgarsky, 2017) , the role of depth and the importance of architecture (Telgarsky, 2016; Safran and Shamir, 2017; Eldan and Shamir, 2016) , and many other topics such as their generalization properties and choice of optimization procedure (Hardt et al., 2016; Zhang et al., 2017; Bartlett et al., 2017) .

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. (Eldan and Shamir, 2016; 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 (Donoho, 2006) .

2. OVERVIEW OF RESULTS:

We will be considering a regression task where the data has a sparse latent structure. More precisely, we wish to fit pairs of (observables, labels) (X, Y ) generated by a (latent-variable) process:

• Sample a latent vector Z ∈ R m from H, where H is a distribution over sparse vectors.

• To produce X ∈ R n , set X = AZ + ξ, where the noise ξ ∼ subG(σ2 ) is a subgaussian random vector with variance proxy σ 2 (e.g. N (0, σ 2 I)). • To produce Y ∈ R, we set Y = w, Z .

We hope the reader is reminded of classical setups like sparse linear regression, compressive sensing and sparse coding: indeed, this distribution on the data distribution X is standard in these setups. In our setting, we additionally attach a regression task to this data distribution, wherein the labels Y are linearly generated 2 by a predictor w from the latent vector Z.

Note our interest is slightly different than usual: in the traditional setup, we are interested in the statistical/algorithmic problem of inferring Z, given X as input (the former studying the optimal rates of "reconstruction" for Z, the latter efficient algorithms for doing so). In particular, we do not typically care about the particular form of the predictor as long as it is efficiently computable.

By contrast, we want to understand how well different subsets of universal approximator families can fit the data points (X, Y ). Namely, regardless of the specifics of the training procedure, the end will be an element of some function class like a linear function of a kernel embedding of X, or a neural network. Therefore, we ask if these classes are rich enough to reconstruct Y given X accurately (i.e. compared to the Bayes-optimal estimator E[Y |X]): if the answer is negative, then we know our predictor will perform poorly, no matter the training method. We measure the performance of these estimators in the natural3 distributional sense: expected reconstruction error,

E[( Ŷ -Y ) 2 ].

Informally, what we will show is the following. Theorem (Informal). For the problem of predicting Y given X in the generative model for data described above, it holds that:

(1) Small two-layer ReLU networks achieve close to the statistically optimal rate.

(2) Polynomial predictors of degree lower than log m achieve a statistical rate which is substantially worse. (In fact, in a certain sense, close to "trivial".) Conversely, polynomial predictors of degree O((log n) 2 ) achieve close to the statistically optimal rate. The lower bound in (2) is relevant since fitting a polynomial to data points of the form (x i , y i ) requires4 searching through the space of multivariate polynomials of degree Ω(log m) which has dimension m Ω(log(m)) , and thus even writing down all of the variables in this optimization problem takes super-polynomial time. Practical aspects of using polynomial kernels even with much lower degree than this have been an important concern and topic of empirical research; see for example (Chang et al., 2010) and references within. On the other hand, the upper bound in (2) shows that our analysis is essentially tight: greater than polylog(m) degree is not required to achieve good statistical performance, which is qualitatively different from the situation in worst-case analyses (see Section 4.2.2 for more details). Our mathematical analysis closely matches the observed behavior in experiments: see Section 6.

For formal statements of the theorems, see Section 4.

3. PRIOR WORK:

There has been a large body of work studying the ability of neural networks to approximate polynomials and various classes of well-behaved functions, such as recent work (Yarotsky, 2017; Safran and Shamir, 2017; Telgarsky, 2017; Poggio et al., 2017) . These results exclusively focus on the worst-case setting where the goal is to find a network close to some function in some norm (e.g. L ∞ or L 1 -norm, often under an adversarially chosen measure).

In contrast there is little work on the problem of approximating ReLU networks by polynomials, mostly because it is well-known by classical results of approximation theory (Newman et al., 1964; DeVore and Lorentz, 1993 ) that polynomials of degree Ω(1/ ) are required to approximate even a single ReLU function within error in L ∞ -norm on [-1, 1]. On the other hand, we will show that if we do not seek to achieve -error everywhere for the ReLU (in particular not near the nonsmooth point at 0) we can build good approximations to ReLU using polynomials of degree only O(log 2 (1/ )) (see discussion in Section 4.2.2 and Theorem 5.2).

Because of the trivial Ω(1/ ) lower bound for worst-case approximation of ReLU networks by polynomials, (Telgarsky, 2017) studied the related problem of approximating a neural network by rational functions. (A classical result of approximation theory (Newman et al., 1964) shows that rational functions of degree O(log 2 (1/ )) can get within -error of the absolute value function.) In particular, (Telgarsky, 2017) shows that rational functions of degree polylog(1/ ) can get within distance in L ∞ -norm of bounded depth ReLU neural networks.

Somewhat related is also the work of (Livni et al., 2014) who considered neural networks with quadratic activations and related their expressivity to that of sigmoidal networks in the depth-2 case building on results of (Shalev-Shwartz et al., 2011) for approximating sigmoids. The result in (Shalev-Shwartz et al., 2011) is also proved using complex-analytic tools, though the details are substantially different.

The work of (Zhang et al., 2016) studied the power of kernel regression methods to simulate a certain class of neural networks. More precisely, they bounded the 2 norm of kernel regression models approximating neural networks with bounded depth, "nice" activation functions (not including ReLU), and small input and edge weights. By standard generalization theory, this gives a corresponding sample complexity result for improper learning via kernels. In our setting, their result does not apply: first, the network of interest has ReLU activations; even ignoring this issue, their bounds would be roughly exponential in n because the 2 norm of the network's input vector is large, of order Θ(σ √ n).5 .

There is a vast literature on high dimensional regression and compressed sensing which we do not attempt to survey, since the main goal of our paper is not to develop new techniques for sparse regression but rather to analyze the representation power of kernel methods and neural networks. Some relevant references for sparse recovery can be found in (Vershynin, 2018; Rigollet, 2017) . We only emphasize that the upper bound via soft thresholding we show (Theorem 4.1) is implicit in the literature on high-dimensional statistics; we include the proofs here solely for completeness.

4. MAIN RESULTS:

In this section we will give formal statements of the results and give some insight into the techniques used.

First, we state the assumptions on the parameters of our generative model:

• Z is sparse: more precisely, |supp(Z)| ≤ k and Z 1 ≤ M with high probability. 6 • A is a µ-incoherent n × m matrix, which means that A A -I ∞ ≤ µ for some µ ≥ 0. • w ∞ = 1 (w.l.o.g., since changing the magnitude of w rescales Y )

The assumption on A is standard in the literature on sparse recovery (see reference texts (Rigollet, 2017; Moitra, 2018) ). In general one needs an assumption like this (or a stronger one, such as the RIP property) in order to guarantee that standard algorithms such as LASSO actually work for sparse recovery. For the reader not familiar with this literature, this property is a proxy for the matrix being "random-like" -e.g. a matrix with i.i.d. entries of the form ±1/ √ n has µ = O(1/ √ n), even when m >> n. We also note that for notational convenience, we will denote A ∞ = max i,j |A i,j |.

Before proceeding to the results, we note that the first-time reader may freely assume that µ = 0 and n = m; the results are still interesting in this setting and no important technical idea is needed for the more general case. For the upper bounds, we have included results for the more general setting (with µ ≥ 0) to show that our results are relevant even to very high-dimensional settings where m >> n. We have only proven the lower bound in the case µ = 0: this is the easiest setting for algorithms, so this makes the lower bounds the strongest.

4.1. REGRESSION USING RELU NETWORKS:

We prove the following theorem, which shows that small 2-layer ReLU networks can achieve an almost optimal statistical rate. Let us denote the soft threshold function with threshold τ as ρ τ (x) := sgn(x) min(0, |x| -τ ) = ReLU(x -τ ) -ReLU(-x + τ ). Let's introduce the notation ρ ⊗m τ to denote the map given by applying ρ τ coordinate-wise to a vector in R m . Consider the following estimator (for y), corresponding to a 2-layer neural network:

ẐNN := ρ ⊗m τ (A X) ŶNN := w, ẐNN

We can prove the following result for the estimator (see Appendix A of the supplement):

Theorem 4.1 (2-layer ReLU). With high probability, the estimator ŶNN satisfies

( ŶNN -Y ) 2 = O((1 + µ)σ 2 k 2 log(m) + µ 2 k 2 M 2 )

Notice that the size of the ReLU net is comparable to the input: one of the layers has the same dimension as A, the other the same dimension as w. Furthermore, to interpret this result, recall that we think of µ as quite small -in particular µ 1. Thus the error of the estimator is essentially O(σ 2 k 2 log(m)), i.e. essentially |σ| error "per-nonzero-coordinate". It can be shown that this upper bound is nearly information-theoretically optimal (see Remark B.1), except that there is an additional factor of k. This additional factor is artificial and can be removed with added technical effort; we show how to do this in the µ = 0 case in Theorem A.1.

We emphasize that the analysis of this kind of soft thresholding estimator is implicit in much of the literature on sparse linear regression. For completeness, we include a complete and self-contained proof of Theorem 4.1 in Section A.

4.2. REGRESSION USING POLYNOMIALS:



4.2.1. LOWER BOUNDS FOR LOW-DEGREE POLYNOMIALS:

We first show that polynomials of degree smaller than O(log m) essentially cannot achieve a "nontrivial" statistical rate. This holds even in the easiest case for the dictionary A: when it's the identity matrix.

More precisely, we consider the situation in which A is an orthogonal matrix (i.e. µ = 0, m = n), w ∈ {±1} m , the noise distribution is Gaussian N (0, σ 2 I), and the entries of Z are independently 0 with probability 1 -k/m and N (0, γ 2 ) with probability k/m. Then we show Theorem 4.2. Suppose k < m/2 and f is a multivariate degree d polynomial. Then

E[(f (X) -Y ) 2 ] ≥ (1/4) γ 2 k 1 + k/m(d + 1) 3d+2 (1 + (γ/σ) d ) 2

To parse the result, observe that the numerator is of order γ 2 k which is the error of the trivial estimator7 and the denominator is close to 1 unless d is sufficiently large with respect to m. More precisely, assuming the signal-to-noise ratio γ/σ does not grow too quickly with respect to m, we see that the denominator is close to 1 unless d d = Ω( √ m), i.e. unless d is of size Ω((log m)/ log log m). On a technical note we observe that this statement is given with respect to expectation but a similar one can be made with high probability, see Remark B.2.

4.2.2. NEARLY MATCHING UPPER BOUNDS:

The lower bound of the previous section leaves open the possibility that polynomials of degree O(polylog(m)) still do not suffice to perform sparse regression and solve our inference problem; Indeed, it is a well-known fact (see e.g. (Telgarsky, 2017) ) that to approximate a single ReLU to -closeness in infinity norm in [-1, 1] requires polynomials of degree poly(1/ ); this follows from standard facts in approximation theory (DeVore and Lorentz, 1993) since ReLU is not a smooth function.

Proceeding with this "worst-case" way of thinking: our upper bound follows by designing a polynomial approximation to ReLU into our neural network construction; since estimates for Y typically accumulate error from estimating each of the m coordinates of Z, to guarantee accurate reconstruction we would need m to be small. Plugging in the the best approximation to ReLU in infinity norm, we would need a Ω( √ m)-degree polynomial for this to yield a multivariate polynomial with similar statistical performance to the 2-layer ReLU network which computes ŶNN . Thus, naively, we might suspect that the degree of the kernel needs to be as high as √ m to get a reasonable approximation.

Surprisingly, we show this intuition is incorrect! In fact, we show how using only a polylog(m) degree polynomial, our converted ReLU network has similar statistical performance. Formally this is summarized by the following theorem, where Ŷd,M is the corresponding version of ŶNN formed by replacing each ReLU by our polynomial approximation.

Theorem 4.3. Suppose τ = Θ(σ (1 + µ) log m+µM ) and d ≥ d 0 = Ω((2+ M τ ) log 2 (M m/τ 2 )). With high probability, the estimator Ŷd,M satisfies 8 ( Ŷd,M -Y ) 2 = O(k 2 ((1 + µ)σ 2 log(m) + µ 2 M 2 ))

The idea behind our construction is described in Section 5.3. Our methods are novel and may be of independent interest; we are not aware of a way to get this result using only generic techniques such as FT-Mollification (Diakonikolas et al., 2010) .

5. OVERVIEW OF PROOFS:

In this section, we will sketch the ideas behind the proofs of our results. The full proofs are relegated to the appropriate appendices. We proceed with each of our results in turn.

5.1. UPPER BOUND FOR RELU NETWORKS:

As previously mentioned, this kind of result is well-known in the literature on sparse regression and we include a proof primarily for completeness. The intuition is simple: the estimator ẐNN can make use of the non-linearity in the soft threshold to zero out the coordinates in the estimate A X which are small and thus "reliably" not in the support of the true z. Thus, the estimator only makes mistakes on the non-zero coordinates. The full proofs are in Section A.

5.2. LOWER BOUND: PROOF SKETCH OF THEOREM 4.2:

The proof of Theorem 4.2 has two main ideas, which we detail below:

(1) A structural lemma, which shows that the optimal predictor has a "decoupled" structure along the coordinates of the latent variable.

(2) An analysis of this decoupled estimator using a bias-variance calculation in an appropriately chosen basis. The full proofs of this Section are in Appendix B.

5.2.1. STRUCTURE OF THE OPTIMAL ESTIMATOR:

As explained above, our structural lemma shows that the optimal low-degree polynomial estimator decouples along the coordinates of the latent variable. In order to understand why this should be true, first observe that the optimal estimator for Y = w, Z given X has a particularly simple structure. Concretely, the optimal estimator is the conditional expectation E[ w, Z |X] = i w i E[Z i |X], so the optimal estimator for Y simply reconstructs Z as well as possible coordinate-wise, then takes an inner product with w.

With this in mind, note the coordinates of Z are independent in our setting, so optimal estimation of Z i should not depend in any way on reconstructing Z j for j = i. This allows us to show that the optimal polynomial of degree d to estimate Y has no "mixed monomials" in an appropriate basis. This is the content of the next lemma, whose proof is in Appendix B. Lemma 5.1. Suppose X = AZ + ξ where A is an orthogonal m × m matrix, Z has independent entries and ξ ∼ N (0, σ 2 Id). Then there exists a unique minimizer f * d over all degree d polynomials f d of the square-loss,

E[(f d (A X) -w, Z ) 2 ]

and furthermore f * d has no mixed monomials. In other words, we can write f

* d (A X) = i f * d,i ((A X) i )

where each of the f * d,i are univariate degree d polynomials.

5.2.2. FOURIER ANALYSIS AND BIAS-VARIANCE TRADE-OFF:

Once we have reduced to considering estimators with decoupled structure, it becomes feasible to analyze the performance of all possible low degree polynomials using a bias-variance calculation in a carefully chosen basis. This is the second (and more involved) step in the proof. In order to perform the calculation, we need to apply Fourier analytic methods, so we need to switch to an orthonormal basis. Since the noise we chose for the lower bound instance is Gaussian9 , a natural choice is the Hermite polynomials.

We review the definition of the Hermite polynomials in Appendix B, but for the purposes of this proof overview, the Hermite polynomials are polynomials H n (x) indexed by multi-indices n ∈ N m 0 with the important property that they are orthogonal with respect to the standard m-variate Gaussian distribution, namely

E X∼N (0,σ 2 I )H n (X/σ)H n (X/σ) = 0, if n = n 1, otherwise

From this, we can derive Plancherel's Theorem in this basis:

Theorem 5.1 (Plancherel's Theorem in Hermite Basis). Let f (x) = n f (n)H n (x/σ), then E X∼N (0,σ 2 I )[|f (X)| 2 ] = n | f (n)| 2

We use this theorem, along with the structural Lemma 5.1 to perform a bias-variance tradeoff analysis of any predictor: namely, we show (1) If the Fourier coefficients | f (n)| are large, then the estimator will be very sensitive to noise (i.e. has too high of a variance).

(2) On the other hand, if | f (n)| is small and f is low-degree, then the estimator cannot match the correct mean well regardless of noise (i.e. has too high of a bias).

Efficient application of Plancherel's theorem is key to proving both results: in the first case, we apply it over the randomness in the noise ξ, and in the second case, we apply it over the randomness in the latent vector Z, which has Gaussian entries conditioned on its support. Note that when f is sufficiently high-degree, it can effectively take advantage of the difference in scales between the noise and the signal to achieve both low bias and low variance simultaneously: see the following upper bound section for details.

5.3. UPPER BOUND: PROOF SKETCH OF THEOREM 4.3:

As previously mentioned, it's a result from classical approximation theory that no low-degree polynomial is close to the ReLU function on all of [-1, 1]. The crux of these results is that it's hard to approximate ReLU well at 0, its point of non-smoothness.

However, in our setting precisely approximating ReLU everywhere is not important for getting a good regression rate: instead, the approximation needs to be very close to 0 when the input is negative, and only very coarsely accurate otherwise. The reason for this is the intuition we described for 2-layer ReLU networks: the property of ReLU that is useful in this setting is it's "denoising" ability -the fact that it zeroes out negative inputs.

Consequently, we design a polynomial approximation to ReLU of degree O(log 2 n) which sacrifices accuracy near the point of non-smoothness in favor of closeness to 0 in the negative region.

More precisely, we prove the following theorem, in which the parameter τ in our theorem controls the trade-off between the polynomial p d being close to 0 for x < 0 and being close to x for x > 0. Theorem 5.2. Suppose R > 0, 0 < τ < 1/2 and d ≥ 7. Then there exists a polynomial

p d = p d,τ,R of degree d such that for x ∈ [-R, 0] |p d (x) -ReLU(x)| ≤ 14R d τ π e - √ πτ d/4

and for x ∈ [0, R],

|p d (x) -ReLU(x)| ≤ 2Rτ + 2R 4τ πd + 12R d τ π e - √ πτ d/4 .

The proof of this theorem proceeds in two steps:

(1) First, one takes a "soft-max" mollification of ReLU of the form g β (x) := 1 β log(1 + e βx ) with an appropriately tuned β, so that g β is sufficiently close to ReLU.

(2) Second, if β is not too large, we prove that the poles (in the complex plane) of the 

6. SIMULATIONS:

Finally, we provide synthetic experiments to verify the predictions from Theorem 4.2 and Theorem 4.3. The setup is as follows: we generate a large synthetic data set (with n = m and µ = 0) in the following fashion:

• A is a random orthogonal matrix and w is sampled from a n-dimensional standard Gaussian.

• Z ∈ R n is sampled by including each coordinate with probability k/n, and sampling a standard Gaussian for each included coordinate.

• X and Y are sampled according to the generative model in Section 2, using Gaussian noise with standard deviation σ.

For each fixed degree, we fit a polynomial using least-squares regression, and evaluate the performance on a corresponding test set10 generated in the same fashion (reusing the same A and w). Solving the regression problem for large degrees is intractable using standard training methods; to overcome this issue, we used structural observation in Lemma 5.1 to reduce the regression problem for estimating Y from X to that of estimating Z i given X i , which is a much lower dimensional problem.11 

The results of the experiment are in Figure 1 , graphed on a log scale. All experiments were run with k = 5 and σ = 0.06. We see that for low degrees, i.e. before our prediction error is close to the information-theoretic limit, the log-error decays roughly linearly with respect to polynomial degree. This matches the prediction of the lower bound in Theorem 4.2 after taking a log of the right-hand-side.

For completeness, we also evaluate the baseline 2-Layer ReLU network described in Section 4.1 in the same experimental setup. Table 1 shows the test error of the baseline 2-Layer ReLU network and, for comparison, the best polynomial of degree 17 in the same experiment. Despite the high degree, the ReLU network is still slightly better.

7. CONCLUSIONS:

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. 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.

Lemma A.2. Suppose A is µ-incoherent i.e. A A -I ∞ ≤ µ. Let z be an arbitrary fixed vector such that z 1 ≤ M and |supp(z)| ≤ k. Suppose x = Az + ξ where ξ ∼ N (0, σ 2 I n×n ). Then for some τ = Θ(σ (1 + µ) log m + µM ) and ẑ = ρ ⊗n τ (A x), with high probability we have ẑ -z ∞ ≤ 2τ and supp(ẑ) ⊂ supp(z).

Proof. Observe that:

A x = z + (A A -I)z + A ξ. Note that entry i of A ξ is A i , ξ where A i 2 2 ≤ (1 + µ) so (A t ξ) i is subgaussian with variance proxy at most σ 2 (1 + µ).

By concentration and union bound, with high probability all coordinates not in the true support are thresholded to 0. Similarly we see that for each of the coordinates in the support, an error of at most 2τ is made.

From the above lemma, we can easily prove the main theorem of this section:

Proof of Theorem 4.1. When the high probability above event happens, we have the following upper bound by Holder's inequality:

| ŶNN -Y | 2 = w| supp(h) , ( ẐNN -Z)| supp(h) 2 ≤ k 2 ẐNN -Z 2 ∞ = O(k 2 ((1+µ)σ 2 log(m)+µ 2 M 2 ))

For the lower bounds we will be interested mostly in the case when µ = 0, i.e. A is orthogonal and so m = n, the coordinates of Z are independent and each is nonzero with probability at most k/n, and the noise is Gaussian. Then the error estimate we had in the previous theorem specializes to O(σ 2 k 2 log(n)), but under these assumptions we know that the information-theoretic optimal is actually σ 2 k log(n). While not very important to the flow of the paper, for completeness we can improve the analysis to eliminate the extra factor of k, without changing the algorithm: Theorem A.1. Suppose A is orthogonal (hence m = n), the coordinates of Z are independent, and ξ ∼ N (0, σ 2 I).

Then E| ŶNN -Y | 2 = O(kσ 2 log(m))

Proof. In this case, we have A X = Z + ξ where ξ ∼ N (0, σ 2 I). Therefore the coordinates of Ẑ are independent of each other, and so we see

E| ŶNN -Y | 2 = i w 2 i E[( ẐNN -Z) 2 i ] ≤ i E[( ẐNN -Z) 2 i ]

.

Let E i denote the event that |ξ | i > τ . Then i E[( ẐNN -Z) 2 i ] = i E[(1 Ei + 1 E C i )( ẐNN -Z) 2 i ] ≤ 4kτ 2 + i E[1 E C i ( ẐNN -Z) 2 i ] = 4kτ 2 + i Pr(1 E C i )E[( ẐNN -Z) 2 i |1 E C i = 1] ≤ 4kτ 2 + i Pr(1 E C i )E[(τ + |X i -Z i |) 2 |1 E C i = 1] ≤ 4kτ 2 + i Pr(1 E C i )(2τ 2 + 2E[|ξ i | 2 |1 E C i = 1]) ≤ 4kτ 2 + i C m (2τ 2 + 2C τ 2 )

where the first inequality follows as in Lemma A.2, the second inequality uses that |ρ τ (x) -x| ≤ τ , the third uses that (a + b) 2 = a 2 + 2ab + b 2 ≤ 2a 2 + 2b 2 by Young's inequality, and the last inequality follows from standard tail bounds on Gaussians. We see the last expression is O(kσ 2 log(m)) so we have proved the result.

B LOWER BOUNDS FOR POLYNOMIAL KERNELS:

In this section, prove the lower bounds for polynomial kernels.

We recall the lower bound instance: the noise distribution is N (0, σ 2 Id) and the distribution for Z is s.t. every coordinate is first chosen to be non-zero with probability k/n, and if it is non-zero, it's set as an independent sample from N (0, γ 2 ). This construction makes Z approximately k-sparse with high probability while making its coordinates independent. We choose A as an arbitrary orthogonal matrix, so m = n. We choose w to be an arbitrary ±1 sign vector, so w 2 i = 1 for every i. As a warmup, we first show that linear predictors, and subsequently fixed low degree polynomials cannot achieve the information-theoretic rate12 of O(σ 2 k log n) -in fact, we will show that they achieve a "trivial" rate. Furthermore, we will show that even if the degree of our polynomials is growing with n, if d = o(log n/ log log n) the state of affairs is similar.

B.1 WARMUP: LINEAR PREDICTORS:

As a warmup, and to illustrate the main ideas of the proof techniques, we first consider the case of linear predictors. (i.e. kernels of degree 1.)

The main idea is to use a bias-variance trade-off: namely, we show that the linear predictor we use, say f (x) = w, x either has to have too high of a variance (when w is large), or otherwise has too high of a bias. (Recall, the bias captures how well the predictor captures the expectation.)

We prove:

Theorem B.1. For any w ∈ R n , E[( w, X -Y ) 2 ] ≥ γ 2 k σ 2 γ 2 (k/n) + σ 2

Before giving the proof, let us see how the theorem should be interpreted.

The trivial estimator which always returns 0 makes error of order γ 2 K and a good estimator (such as thresholding) should instead make error of order σ 2 K log n when γ >> σ √ log n. The next theorem shows that as long as the signal to noise ratio is not too high, more specifically as long as γ 2 (k/n) = o(σ 2 ), any linear estimator must make square loss of Ω(γ 2 k), i.e. not significantly better than the trivial 0 estimate.

Note that the most interesting (and difficult) regime is when the signal is not too much larger than the noise, e.g. γ 2 = σ 2 polylog(n) in which case it is definitely true that γ 2 (k/n) << σ 2 .

Proof. Note that w, x -y = w, Az + ξ -w, z = A w -w, z + w, ξ which gives the following bias-variance decomposition for the square loss:

E[( w, x -y) 2 ] = E[( A w -w, z + w, ξ ) 2 ] = E[ A w -w, z 2 + w, ξ 2 ] = k n γ 2 A w -w 2 2 + σ 2 w 2 2 = k n γ 2 w -Aw 2 2 + σ 2 w 2 2

where in the second-to-last step we used that the covariance matrix of Z is γ 2 (k/n)I, and in the last step we used that A is orthogonal. Now observe that if we fix R = w 2 , then by the Pythagorean theorem the minimizer of the square loss is given by the projection of Aw onto the R-dilated unit sphere, so w = R 2 /m(Aw) since Aw 2 = w 2 = √ m. In this case the square loss is then of the form

k n γ 2 R 2 /m(Aw) -Aw 2 2 + σ 2 w 2 2 = k n γ 2 (R - √ m) 2 + σ 2 R 2

and the risk is minimized when

0 = 2 k n γ 2 (R - √ m) + 2σ 2 R i.e. when R = γ 2 (k/n) γ 2 (k/n) + σ 2 √ m so the minimum square loss is ( √ m -R)σ 2 R + σ 2 R 2 = σ 2 γ 2 k γ 2 (k/n) + σ 2 since m = n.

B.2 STRUCTURE OF THE OPTIMAL ESTIMATOR: PROOF OF LEMMA 5.1

Proof of Lemma 5.1. Let X = A X, so by orthogonality X = Z + ξ where ξ ∼ N (0, σ 2 Id).

Observe that if we look at the optimum over all functions f , we see that

min f E[(f (X ) -w, Z ) 2 ] = E[(E[ w, Z |X ] -w, Z ) 2 ] = E[( i w i E[Z i |X ] -w, Z ) 2 ] = E[( i w i E[Z i |X i ] -w, Z ) 2 ].

where where in the first step we used that the conditional expectation minimizes the squared loss, in the second step we used linearity of conditional expectation, and in the last step we used that Z i is independent of X =i .

By the Pythagorean theorem, the optimal degree d polynomial f * d is just the projection of i w i E[Z i |X i ] onto the space of degree d polynomials. On the other hand observe that

E[( i w i E[Z i |X i ] -w, Z ) 2 ] = i w 2 i E[(E[Z i |X i ] -Z i ) 2 ] so the optimal projection f * d is just i w i f * i,d (X i ) where f * i,d is just the projection of each of the E[Z i |X i ]. Therefore f *

d has no mixed monomials. Remark B.1. The previous calculation shows additionally that the problem of minimizing the squared loss for predicting Y is equivalent to that of minimizing the squared loss for the sparse regression problem of recovering Z. It is a well-known fact that the information theoretic rate for sparse regression (with our normalization convention) is Θ(σ 2 k) (see for example (Rigollet, 2017) ), and so the information-theoretic rate for predicting Y is the same, and is matched by Theorem A.1.

B.3 BIAS-VARIANCE, FOURIER ANALYSIS AND PROOF OF THEOREM 4.2:

We recall that the lower bound for polynomials combines the observation of Lemma 5.1 with a bias-variance tradeoff calculation using Fourier analysis on orthogonal polynomials. Concretely, since the noise we chose for the lower bound instance is Gaussian, the most convenient basis will be the Hermite polynomals.

We recall the probabilist's Hermite polynomial He n (x), defined by the recurrence relation

EQUATION

where He 0 (x) = 1, He 1 (x) = x. In terms of this, the normalized Hermite polynomial H n (x) is

H n (x) = 1 √ n! He n (x).

Let H n (x) for a vector of indices n ∈ N m 0 denote the multivariate polynomial Π m i=1 H ni (x i ). It's easy to see the polynomials H n (x) form an orthogonal basis with respect to the standard m-variate Gaussian distribution. As a consequence, we get

E X∼N (0,σ 2 I )H n (X/σ)H n (X/σ) = 0, if n = n 1, otherwise

which gives us Plancherel's theorem:

Theorem B.2 (Plancherel in Hermite basis). Let f (x) = n f (n)H n (x/σ), then E X∼N (0,σ 2 I )[|f (X)| 2 ] = n | f (n)| 2

We can use Plancherel's theorem to get lower bounds on the noise sensitivity of degree d polynomials.

This will be an analogue of the variance.

Lemma B.1. [Variance analogue in Hermite basis] Let f (x) = n f (n)H n (x/σ) and let f =0 := f -f (0). Then E[(f (A X) -Y ) 2 ] ≥ (1 -k/n) f =0 2 2

Proof. First we suppose Z (and thus Y ) is fixed and consider the randomness of the noise. Let S denote the support of Z. Recall that A x = Z + ξ where ξ ∼ N (0,

σ 2 I n×n ). Define f Z (ξ) := f (Z + ξ) -Y , then by Plancherel E ξ [(f (A x) -Y ) 2 ] = E ξ [f Z (ξ ) 2 ] = n | f Z (n)| 2 Furthermore n | f Z (n)| 2 ≥ n:supp(n) ⊂S | f (n)| 2 because (ξ + Z)| S c = ξ | S c

so by expanding out f Z in terms of the fourier expansion of f , we see f Z (n) = f (n) for n such that supp(n) ⊂ S. Finally the probability n ⊂ S for n = 0 is upper bounded by the probability a single element of its support is in S, which is k/n. Therefore

E Z,ξ [(f (A x) -Y ) 2 ] ≥ n | f (n)| 2 E[1 supp(n) ⊂S ] ≥ n =0 (1 -k/n)| f (n)| 2

which proves the result.

Next we give a lower bound for the bias, showing that if f =0 2 2 is small for a low-degree polynomial, it cannot accurately predict y. Here we will assume f is of the form given by Lemma 5.1. Lemma B.2 (Low variance implies high bias). Suppose f is a multivariate polynomial of degree d with no mixed monomials, i.e. f (x) = i f i (x i ) where f i is a univariate polynomial of degree d. Expand f in terms of Hermite polynomials as f

(x) = n f (n)H n (x/σ). Then E[(f (A X) -Y ) 2 ] ≥ (k/n) n i=1 w 2 i max(0, γ - n i=1 | f (ke i )| 2 (d + 1) 3d+2 (1 + (γ/σ) d )) 2

Before proving the lemma, let us see how it proves the main theorem:

Proof of Theorem 4.2. By Lemma 5.1, Lemma B.1, and Lemma B.2 we have that for the f which minimizes the square loss among degree d polynomials, we have a variance-type lower bound

E[(f (A X) -Y ) 2 ] ≥ (1 -k/n) n i=1 d k=1 | f (ke i )| 2

and (using that w 2 i = 1 to simplify) a bias-type lower bound

E[(f (A X) -Y ) 2 ] ≥ (k/n) n i=1 max(0, γ - n i=1 | f (ke i )| 2 (d + 1) 3d+2 (1 + (γ/σ) d )) 2 . Let f i 2 := n i=1 | f (ke i )| 2 .

Then averaging these lower bounds and simplifying using k < n/2 gives

E[(f (A X) -Y ) 2 ] ≥ (1/4) n i=1 max( f i 2 , k/n(γ -f i 2 (d + 1) 3d+2 (1 + (γ/σ) d ))) 2 ≥ (1/4) n i=1 γ 2 (k/n) (1 + k/n(d + 1) 3d+2 (1 + (γ/σ) d )) 2 ≥ (1/4) γ 2 k (1 + k/n(d + 1) 3d+2 (1 + (γ/σ) d )) 2

Returning to the proof of Lemma B.2, we have:

Proof of Lemma B.2. Since f has no mixed monomials, we get for the Hermite expansion that

f (n) = 0 unless |supp(n)| ≤ 1. Let X := A X = Z + ξ where ξ ∼ N (0, σ 2 I). Next observe by independence that E[(f (X ) -Y ) 2 ] = i w 2 i E[(f i (X i ) -Z i ) 2 ] ≥ (k/n) i w 2 i E[(f i (X i ) -Z i ) 2 |Z i = 0]

where the last inequality follows since there is a k/n chance that Z i ∼ N (0, σ 2 I), equivalently that Z i = 0. By the conditional Jensen's inequality we have

(k/n) i w 2 i E[(f i (X i ) -Z i ) 2 |Z i = 0] ≥ (k/n) i w 2 i E[(E[f i (X i )|Z i ] -Z i ) 2 |Z i = 0]. Observe that f i (X i ) = d k=0 f (ke i )H k (Z i /σ + ξ/σ) and let g i (Z i ) := E[f i (X i )|Z i ] -Z i ,

so then g i is a polynomial of degree d in Z i . Write the Hermite polynomial expansion of g i in terms of H k (Z i /γ) as

g i (x) = d k=0 g i (k)H k (Z i /γ),

then by Plancherel's formula

(k/n) i w 2 i E[(E[g(Z i ) -Z i ) 2 |Z i = 0] = (k/n) i w 2 i d k=0 | g i (k)| 2 ≥ (k/n) i w 2 i | g i (1)| 2

and it remains to lower bound | g i (1)|. By orthogonality and direct computation,

g i (1) = E Zi∼N (0,γ) [(E[f i (X i )|Z i ] -Z i )H 1 (Z i /γ)] = -γ + E Zi∼N (0,γ) [E[f i (X i )|Z i ](Z i /γ)].

Now we upper bound the last term

E Zi∼N (0,γ) [E[f i (X i )|Z i ](Z i /γ)] = f (0)E[Z i /γ] + d k=1 f (ke i )E Zi∼N (0,γ) [E[H k (Z i /σ + ξ /σ)|Z i ](Z i /γ)] = d k=1 f (ke i )E Zi∼N (0,γ) [H k (Z i /σ + ξ /σ)(Z i /γ)] ≤ d k=1 | f (ke i )| 2 1/2 d k=1 E Zi∼N (0,γ) [H k (Z i /σ + ξ /σ)(Z i /γ)] 2 1/2

where the second equality is by the law of total expectation and the last inequality is Cauchy-Schwarz.

Using the recurrence relation (1), we can bound the sum of the absolute value of the coefficients of

H k (x) by k k / √ k! ≤ k k .

We can also bound the moments of the absolute value of a Gaussian by E ξ∼N (0,1) [|ξ| k ] ≤ k k . Therefore by Holder's inequality

E Zi∼N (0,γ) [H k (Z i /σ + ξ /σ)(Z i /γ)] ≤ k k k sup =1 |E Zi∼N (0,γ) [(Z i /σ + ξ /σ) (Z i /γ)]| ≤ k k k sup =1 E Zi∼N (0,γ) [(|Z i |/σ + |ξ |/σ) (|Z i |/γ)] ≤ 2 k k k k sup =1 (E Zi∼N (0,γ) [|Z i | +1 /σ γ] + E Zi∼N (0,γ) [|ξ | |Z i |/σ γ)]) ≤ 2 k k k [max(1, (γ/σ) k )(k + 1) k+1 + k k ] ≤ (k + 1) 3k+1 (1 + (γ/σ) k ).

Therefore by reverse triangle inequality

| ĝi (1)| 2 ≥ max(0, γ - n i=1 | f (ke i )| 2 (d + 1) 3d+2 (1 + (γ/σ) d )) 2 .

Remark B.2. Remarks on results:

We make a few remarks regarding the results in this section. Recall that γ 2 k is the square loss of the trivial zero-estimator. Suppose as before that γ = Θ(σ 2 polylog(n)), then we see that if d = o(log n/ log log n) then the denominator of the lower bound tends to 1, hence any such polynomial estimator has a rate no better than that of the trivial zero-estimate.

It is possible to derive a similar statement to Theorem 4.2 that holds with high probability instead of in expectation for polynomials of degree o(log n/ log log n). All that is needed is to bound the contribution to the expectation from very rare tail events when the realization of the noise ξ is atypically large. Since the polynomials we consider are very low degree o(log n/ log log n), they can only grow at a rate of x d = x o(log(n)/ log log n) ; thus standard growth rate estimates (e.g. the Remez inequality) combined with the Gaussian tails of the noise can be used to show that a polynomial which behaves reasonably in the high-probability region (e.g. which has small w.h.p. error) cannot contribute a large amount to the expectation in the tail region.

C UPPER BOUNDS FOR POLYNOMIAL KERNELS:

In this section, we construct polynomials achieving close to the information-theoretic optimal rate of degree only O(log 2 m). Recall this is nearly optimal due to our previous lower bound of Ω(log n).

As previously mentioned, the key technical result here will be Theorem 5.2, giving the construction of a new polynomial approximation to ReLU. Before proceeding to the proof of that theorem, we show how it implies the final result, Theorem 4.3.

Towards that, we substitute our polynomial construction for ρ τ into our ReLU neural network and derive the analogous version of Lemma A. Thus we see that taking d = Ω( Mτ τ log2 ( Mτ τ )) suffices to make the latter expression at most . Similarly for |x| > τ we know that

|ρ d,τ,M (x)| ≤ 2τ + 2M τ 4τ M τ πd + 26M τ dM τ τ π e - √ πτ d/4Mτ

and taking d = Ω( Mτ τ log 2 ( Mτ τ )) with sufficiently large constant guarantees the middle term is at most τ and the last term is at most . Using this, we can show that if we use a polynomial of degree Ω((M/σ √ log n) log 2 m) we can achieve similar statistical performance to the ReLu network: Lemma C.2. Suppose A is µ-incoherent i.e. A A -Id ∞ ≤ µ. Let z be an arbitrary fixed vector such that z 1 ≤ M and |supp(z)| ≤ k. Suppose x = Az + ξ where ξ ∼ N (0, σ 2 Id n×n ). Then for some τ = Θ(σ (1 + µ) log m + µM ), for any d ≥ d 0 = Ω( Mτ τ log 2 (M τ m/τ 2 )), if we take ẑ := ρ⊗n d,τ,M (A x), then with high probability we have ẑ -z 1 ≤ 6kτ .

Proof. Apply Lemma C.1 with = τ /m. Then we see for |x| ∈ (τ, M τ ) we havn

|ρ d,τ,M (x) -x| ≤ (3 + 1/m)τ ≤ 4τ and for |x| ≤ τ we have |ρ d,τ,M (x)| ≤ τ /m Observe that A x = z + (A A -Id)z + A ξ.

Note that entry i of A ξ is A i , ξ where A i By choosing τ with sufficiently large constant, then applying the sub-Gaussian tail bound and union bound, with high probability all coordinates not in the true support are thresholded to at most τ /m. Similarly we see that for each of the coordinates in the support, an error of at most 5τ is made. Therefore ẑ -z 1 ≤ 5kτ + m(τ /m) ≤ 6kτ .

Now we have all the ingredients to prove Theorem 4.3:

Proof of Theorem 4.3. Define an estimate for Y by taking Ẑd,M := ρ⊗n d,τ,M (A X) where τ is defined as in the Lemma, and then taking Ŷd,M := w, Ẑd,M . Applying the previous Lemma, we get analogous versions of Theorem 4.1 by the same argument as in that theorem.

Finally, we return to the proof of the key Theorem 5.2: Proof of Theorem 5.2. We start with the case where R = 1/2. We build the approximation in two steps. First we approximate ReLu by the following "annealed" version of ReLu, for parameters β > π, τ > 0 to be optimized later:

g β (x) = 1 β log(1 + e βx )

f β,τ (x) = g β (x -τ ).

Observe that when we look at negative inputs, g β (-x) = 1 β log(1 + e -βx ) ≤ 1 β e -βx . Therefore when x < 0, f β (x) ≤ 1 β e -βτ . For the second step,, we need to show f β can be well-approximated by low-degree polynomials. In fact, because f β is analytic in a neighborhood of the origin, it turns out that its optimal rate of approximation is determined exactly by its complex-analytic properties. More precisely, define D ρ to be the region bounded by the ellipse in C = R 2 centered at the origin with equation The proof is fairly simple: by writing f in terms of cos(x) one gets an expansion into Chebyshev polynomials and it suffices to bound the coefficients of the corresponding Fourier series: to do this, we write them as integrals over the unit circle, and use the analyticity assumption on D ρ1 to contour shift the integral to a different circle, which immediately gives us the desired exponential decay. For details see (DeVore and Lorentz, 1993) .

We will now apply this theorem to g β . First, we claim that g β is analytic on D ρ1 where ρ 1 is the solution to this equation for the semi-axis of the ellipse:

1 2 (ρ -ρ -1 ) = π 2β

which is

ρ 1 = 4β 2 + π 2 + π 2β > 1 + π/2β.

To see this, first extend log to the complex plane by taking a branch cut at (-∞, 0]. To prove g β is analytic on D ρ1 , we just need to prove that 1 + e βz avoids (-∞, 0] for z ∈ D ρ1 . This follows because by the definition of ρ 1 , for every z ∈ D ρ1 , (z) < π 2β hence (1 + e βz ) ≥ 1. We also see that for z ∈ D ρ1 , 

:

One could also imagine producing discrete labels by applying a softmax operation. We stick to the regression setting for reasons of technical simplicity and leave generalizing our results to future work.

This is natural because it is the (only) loss which the conditional expectation E[Y |X] minimizes. In statistical language, we are asking about the minimum excess risk achievable by estimators in our function class.

We note that for kernel ridge regression, one can use the kernel trick to reduce to train in a space with dimension equal to the size of the training dataset. However, since training data sets are often very large, this is not necessarily helpful. More usefully, in the classification context, the optimization may become feasible due to the existence of a smaller number of support vectors. In this case, the ability of algorithms to efficiently find a good function depends on more complex interactions between the particular choice of kernel and the margin properties of the data; we leave analyzing these kinds of quantities for future work.

See Proposition 1 ofZhang et al. (2016)

The assumed 1-norm bound M plays a minor role in our bounds and is only used when the incoherence µ > 0.

I.e. the estimator which always returns 0, without looking at the data.

As in Theorem 4.1, there is a spurious factor of k in this bound which can be removed with additional technical effort. In particular in the µ = 0 case we can remove it using the same argument as Theorem A.1; details are omitted.

The proof does not rely heavily on this choice; as long as we choose the correct orthogonal basis of polynomials, the proof would go through with minor modifications.

Small technical remark: our upper bound (Theorem 4.3) is with-high-probability and not in expectation, so we drop the outlier 1 percent of test results which had largest error. The reason is that we may draw a rare tail event where the input is unusually large/non-sparse and then the polynomial predictor may make an exponentially large error in the degree.

Another technical remark: we only run the experiment for odd degrees, since the optimal estimator is an odd function.

See Remark B.1 for why this is the optimal information-theoretic rate.

≤ (1 + µ) so (A t ξ) i is Gaussian with variance at most σ 2 (1 + µ).

Figures and Tables:

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.

2. First, define M τ = M + 2τ and let ρd,τ,M = p d,τ /Mτ ,Mτ (x -τ ) + p d,τ /Mτ ,Mτ (-x + τ ) where p is the polynomial constructed in Theorem 5.2. We then have: Lemma C.1. Suppose , τ > 0 and M ≥ 1. Then for all d ≥ d 0 = Ω( Mτ τ log 2 ( Mτ τ )), for |x| ∈ (τ, M τ ) we have |ρ d,τ,M (x) -x| ≤ 3τ + and for |x| ≤ τ we have |ρ d,τ,M (x)| ≤ Proof. By the guarantee of Theorem 5.2, we see that for for |x| ≤ τ that |ρ d,τ,M (x)| ≤ 28M τ dM τ

axes a = 1 2 (ρ + ρ -1 ) and b = 1 2 |ρ -ρ -1 |; the focii of the ellipse are ±1. For an arbitrary function f : [-1, 1] → R, let E d (f ) denote the error of the best polynomial approximation of degree d in infinity norm on the interval [-1, 1] of f . Then the following theorem of Bernstein exactly characterizes the growth rate of E d (f ): Theorem C.1 (Theorem 7.8.1, (DeVore and Lorentz, 1993)). Let f be a function defined on [-1, 1]. Let ρ 0 be the supremum of all ρ such that f has an analytic extension on D ρ . Then lim sup d→∞ d E d (f ) = 1 ρ For our application we need only the upper bound and we need a quantitative estimate for finite n. Following the proof of the upper bound in (DeVore and Lorentz, 1993), we get the following result: Theorem C.2. Suppose f is analytic on the interior of D ρ1 and |f (z)| ≤ M on the closure of D ρ1 . Then E d (f ) ≤ 2M ρ 1 -1 ρ -n 1

last step we used that 1 + x ≥ exp(x/2) for x < 1/2 and that β > π. Let gβ,d denote the best polynomial approximation to g β of degree d and let fβ,τ,d = gβ,d (x -τ )Thus for x ∈ [-1 + τ, 0], |ReLu(x) -fβ,τ,d (x)| ≤ |f β,τ (x)| + |g β,d (x -τ ) -g β,τ (x -τ )| ≤ 1 β e -βτ + 12β π e -πd/4βTake β = πd/4τ and require d > 7 so that β > 1, then for x ∈ [-1 + τ, 0],|ReLu(x) -fβ,τ,d (x)| ≤ 7For x ∈ (0, 1 -τ ] we have by the 1-Lipschitz property of g β and calculus that|x -f β,τ (x)| ≤ τ + |x -g β (x)| ≤ τ + log 2 β so |ReLu(x) -fβ,τ,d (x)| ≤ |x -f β,τ (x)| + |g β,d (x -τ ) -g β,τ (x -τ )| ≤ τPlugging in our value of β and using log 2 ≤ 1 gives |ReLu(x) -fβ,τ,d (x)| ≤ τ Now the result for general R follows by taking p d (x) = 2R fβ,τ,d (x/2R), since 2R•ReLu(x/2R) = ReLu(x) and [-1/2, 1/2] ⊂ [-1 + τ, 1 -τ ].

function g β are Test errors of baseline ReLU network (Section 4.1) and Degree 17 polynomial kernel; error is unnormalized. Experiments were run for n up to 4096 and the error between the two methods continued to be similar -results are omitted for concision. not too close to the origin. This, it turns out, governs the polynomial approximability of g β due to a powerful theorem of Bernstein in complex analysis. (See Theorem C.1, and it's quantitative analogue we prove as Theorem C.2.) Once we have this approximation to ReLU, we directly plug it into our 2-Layer ReLU network estimator from Section 4.1 to prove Theorem 4.3.

Table content: <table><tr><td colspan="2">Published as a conference paper at ICLR 2019</td><td/><td/><td/><td/></tr><tr><td>Dimension (n)</td><td>32</td><td>45</td><td>64</td><td>91</td><td>128</td></tr><tr><td colspan="6">2-Layer ReLU Network 6.500282 6.969625 7.479449 8.324109 8.969790</td></tr><tr><td>Degree 17 Polynomial</td><td colspan="5">7.258900 7.723297 8.727798 9.993010 10.256913</td></tr><tr><td colspan="2">The full proofs are in Appendix C.</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 This paper studies the problem of understanding the representation power of neural nets with Relu activations for representing structured data. In order to formalize this, the authors consider data generated from a sparse generative model as follows: A sparse m-dimensional vector Z is sampled from a distribution over sparse vectors. In input X is formed as AZ, where A is an incoherent matrix. The corresponding output is Y= w. X. The goal is to fit the data of the form (X_i, Y_i). The main result of the paper is that a 2-layer ReLU network can fit the data with near optimal error. On the other hand, low degree polynomials~(of degree up to log m) cannot fit the data with non-trivial error. Finally, the authors also show that polynomials of degree polylog(m) can, in fact, fit the data as well as a 2-layer ReLU network. The paper is well written and provides new insights into the representation power of neural nets. It is also nice to know that ReLU networks can be approximated by low degree polynomials in the non-worst case scenario. This is a good paper and I recommend acceptance.