Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

Introduction

Deep learning, in the form of artificial neural networks, has seen a dramatic resurgence in the past recent years, achieving great performance improvements in various fields of artificial intelligence such as computer vision and speech recognition. While empirically successful, our theoretical understanding of deep learning is still limited at best.

An emerging line of recent works has studied the expressive power of neural networks: What functions can and cannot be represented by networks of a given architecture (see related work section below). A particular focus has been the trade-off between the network’s width and depth: On the one hand, it is well-known that large enough networks of depth $2$ can already approximate any continuous target function on $\left[0,1\right]^{d}$ to arbitrary accuracy (Cybenko, 1989; Hornik, 1991). On the other hand, it has long been evident that deeper networks tend to perform better than shallow ones, a phenomenon supported by the intuition that depth, providing compositional expressibility, is necessary for efficiently representing some functions. Indeed, recent empirical evidence suggests that even at large depths, deeper networks can offer benefits over shallower networks (He et al., 2015).

To demonstrate the power of depth in neural networks, a clean and precise approach is to prove the existence of functions which can be expressed (or well-approximated) by moderately-sized networks of a given depth, yet cannot be approximated well by shallower networks, even if their size is much larger. However, the mere existence of such functions is not enough: Ideally, we would like to show such depth separation results using natural, interpretable functions, of the type we may expect neural networks to successfully train on. Proving that depth is necessary for such functions can give us a clearer and more useful insight into what various neural network architectures can and cannot express in practice.

In this paper, we provide several contributions to this emerging line of work. We focus on standard, vanilla feedforward networks (using some fixed activation function, such as the popular ReLU), and measure expressiveness directly in terms of approximation error, defined as the expected squared loss with respect to some distribution over the input domain. In this setting, we show the following:

We show that this depth/width trade-off can also be observed experimentally: Specifically, that the indicator of a unit ball can be learned quite well using a 3-layer network, using standard backpropagation, but learning the same function with a 2-layer network (even if much larger) is significantly more difficult. Our theoretical result indicates that this gap in performance is due to approximation error issues. This experiment also highlights the fact that our separation result is for a natural function that is not just well-approximated by some 3-layer network, but can also be learned well from data using standard methods.

Finally, we prove that any member of a wide family of non-linear and twice-differentiable functions (including for instance $x\mapsto x^{2}$ in $$), which can be approximated to accuracy$\epsilon$using ReLU networks of depth and width$\mathcal{O}(\text{poly}(\log(1/\epsilon)))$, cannot be approximated to similar accuracy by constant-depth ReLU networks, unless their width is at least$\Omega(\text{poly}(1/\epsilon))$. We note that a similar result appeared online concurrently and independently of ours in Yarotsky (2016); Liang & Srikant (2016), but the setting is a bit different (see related work below for more details).

A noteworthy paper in the same setting as ours is Telgarsky (2016), which proves a separation result between the expressivity of ReLU networks of depth $k$ and depth $o\left(k/\log\left(k\right)\right)$ (for any $k$). This holds even for one-dimensional functions, where a depth $k$ network is shown to realize a saw-tooth function with $\exp(\mathcal{O}(k))$ oscillations, whereas any network of depth $o\left(k/\log\left(k\right)\right)$ would require a width super-polynomial in $k$ to approximate it by more than a constant. In fact, we ourselves rely on this construction in the proofs of our results in Sec. 5. On the flip side, in our paper we focus on separation in terms of the accuracy or dimension, rather than a parameter $k$. Moreover, the construction there relies on a highly oscillatory function, with Lipschitz constant exponential in $k$ almost everywhere. In contrast, in our paper we focus on simpler functions, of the type that are likely to be learnable from data using standard methods.

Our separation results in Sec. 5 (for smooth non-linear functions) are closely related to those of Yarotsky (2016); Liang & Srikant (2016), which appeared online concurrently and independently of our work, and the proof ideas are quite similar. However, these papers focused on $L_{\infty}$ bounds rather than $L_{2}$ bounds. Moreover, Yarotsky (2016) considers a class of functions different than ours in their positive results, and Liang & Srikant (2016) consider networks employing a mix of ReLU and threshold activations, whereas we consider a purely ReLU network.

Another relevant and insightful work is Poggio et al. (2016), which considers width vs. depth and provide general results on expressibility of functions with a compositional nature. However, the focus there is on worse-case approximation over general classes of functions, rather than separation results in terms of specific functions as we do here, and the details and setting is somewhat orthogonal to ours.

Preliminaries

for some parameters $v_{1},b_{1},\ldots,v_{n_{1}},b_{n_{1}}$ and $d$-dimensional vectors $\mathbf{w}_{1},\ldots,\mathbf{w}_{n_{1}}$. Similarly, a 3-layer ReLU network has the form

for some parameters $\{u_{i},v_{i,j},b_{i,j},c_{i},\mathbf{w}_{i,j}\}$.

We note that the assumptions from Eldan & Shamir (2016) are very mild, and apply to all standard activation functions, including ReLU, sigmoid and threshold.

Let $\hat{A}$ and $\hat{\mathbf{b}}$ be a $d\times d$ non-singular matrix and vector respectively, to be determined later. We begin by performing a change of variables, $\mathbf{y}=\hat{A}\mathbf{x}+\hat{\mathbf{b}}\iff\mathbf{x}=\hat{A}^{-1}(\mathbf{y}-\hat{\mathbf{b}})$, $d\mathbf{x}=\left|\det\left(\hat{A}^{-1}\right)\right|\cdot d\mathbf{y}$, which yields

In particular, let us choose the distribution $\gamma$ defined as $\gamma(\mathbf{z})=|\det(\hat{A})|\cdot\mu(\hat{A}\mathbf{z}+\hat{\mathbf{b}})$, where $\mu$ is the (continuous) distribution used in the main result of Eldan & Shamir (2016) (note that $\gamma$ is indeed a distribution, since $\int_{\mathbf{z}}\gamma\left(\mathbf{z}\right)=(\det(\hat{A}))\int_{\mathbf{z}}\mu(\hat{A}\mathbf{z}+\hat{\mathbf{b}})d\mathbf{z}$, which by the change of variables $\mathbf{x}=\hat{A}\mathbf{z}+\hat{\mathbf{b}}$, $d\mathbf{x}=|\det(\hat{A})|d\mathbf{z}$ equals $\int_{\mathbf{x}}\mu(\mathbf{x})d\mathbf{x}=1$). Plugging the definition of $\gamma$ in Eq. (1), and using the fact that $|\det(\hat{A}^{-1})|\cdot|\det(\hat{A})|=1$, we get

we get by Eq. (4) and the triangle inequality that

The proof of the theorem appears in Subsection 6.1.

In this subsection, we empirically demonstrate that indicator functions of balls are indeed easier to learn with a 3-layer network, compared to a 2-layer network (even if the 2-layer network is significantly larger). This indicates that the depth/width trade-off for indicators of balls, predicted by our theory, can indeed be observed experimentally. Moreover, it highlights the fact that our separation result is for simple natural functions, that can be learned reasonably well from data using standard methods.

We trained $5$ ReLU networks on this dataset:

One 3-layer network, with a first hidden layer of size $100$, a second hidden layer of size $20$, and a linear output neuron.

Four 2-layer networks, with hidden layer of sizes $100,200,400$ and $800$, and a linear output neuron.

The results are presented in Fig. 1. As can be clearly seen, the 3-layer network achieves significantly better performance than the 2-layer networks. This is true even though some of these networks are significantly larger and with more parameters (for example, the 2-layer, width 800 network has ~80K parameters, vs. ~10K parameters for the 3-layer network). This gap in performance is the exact opposite of what might be expected based on parameter counting alone. Moreover, increasing the width of the 2-layer networks exhibits diminishing returns: The performance improvement in doubling the width from 100 to 200 is much larger than doubling the width from 200 to 400 or 400 to 800. This indicates that one would need a much larger 2-layer network to match the 3-layer, width 100 network’s performance. Thus, we conclude that the network’s depth indeed plays a crucial role, and that 3-layer networks are inherently more suitable to express indicator functions of the type we studied.

Having considered functions depending on the $L_{2}$ norm, we now turn to consider functions depending on the $L_{1}$ norm. Focusing on ReLU networks, we will show a certain separation result holding for any non-linear function, which depends on the input $\mathbf{x}$ only via its 1-norm $\left\|\mathbf{x}\right\|_{1}$.

Then there exists a distribution $\gamma$ over $\{\mathbf{x}:\left\|\mathbf{x}\right\|_{1}\leq(1+\epsilon)r\}$, such that if a 2-layer ReLU network $F(\mathbf{x})$ satisfies

Intuitively, the proof relies on showing that any good $2$-layer approximation of $f(\left\|\mathbf{x}\right\|_{1})$ must capture the non-linear behavior of $f$ close to “most” points $\mathbf{x}$ satisfying $\left\|\mathbf{x}\right\|_{1}\approx r$. However, a $2$-layer ReLU network $\mathbf{x}\mapsto\sum_{j=1}^{N}a_{j}\left[\left\langle\mathbf{w}_{j},\mathbf{x}\right\rangle+b_{j}\right]_{+}$ is piecewise linear, with non-linearities only at the union of the $N$ hyperplanes $\cup_{j}\{\mathbf{x}:\left\langle\mathbf{w}_{j},\mathbf{x}\right\rangle+b_{j}=0\}$. This implies that “most” points $\mathbf{x}$ s.t. $\left\|\mathbf{x}\right\|_{1}\approx r$ must be $\epsilon$-close to a hyperplane $\{\mathbf{x}:\left\langle\mathbf{w}_{j},\mathbf{x}\right\rangle+b_{j}=0\}$. However, the geometry of the $L_{1}$ ball $\{\mathbf{x}:\left\|\mathbf{x}\right\|=r\}$ is such that the $\epsilon$ neighborhood of any single hyperplane can only cover a “small” portion of that ball, yet we need to cover most of the $L_{1}$ ball. Using this and an appropriate construction, we show that required number of hyperplanes is at least $1/\epsilon$, as long as $\epsilon>\exp(-\mathcal{O}(d))$ (and if $\epsilon$ is smaller than that, we can simply use one neuron/hyperplane for each of the $2^{d}$ facets of the $L_{1}$ ball, and get a covering using $2^{d}$ neurons/hyperplanes). The formal proof appears in Subsection 6.2.

We note that the bound in Thm. 3 is of a weaker nature than the bound in the previous section, in that the lower bound is only polynomial rather than exponential (albeit w.r.t. different problem parameters: $\epsilon$ vs. $d$). Nevertheless, we believe this does point out that $L_{1}$ balls also pose a geometric difficulty for 2-layer networks, and conjecture that our lower bound can be considerably improved: Indeed, at the moment we do not know how to approximate a function such as $\mathbf{x}\mapsto[\left\|\mathbf{x}\right\|_{1}-1]_{+}$ with 2-layer networks to better than constant accuracy, using less than $\Omega(2^{d})$ neurons.

In this section, we establish a depth separation result for approximating continuously twice-differentiable ($C^{2}$) functions using ReLU neural networks. Unlike the previous results in this paper, the separation is for depths which can be larger than 3, depending on the required approximation error. Also, the results will all be with respect to the uniform distribution $\mu_{d}$ over $^{d}$. As mentioned earlier, the results and techniques in this section are closely related to the independent results of Yarotsky (2016); Liang & Srikant (2016), but our emphasis is on $L_{2}$ rather than $L_{\infty}$ approximation bounds, and we focus on somewhat different network architectures and function classes.

Clearly, not all $C^{2}$ functions are difficult to approximate (e.g. a linear function can be expressed exactly with a 2-layer network). Instead, we consider functions which have a certain degree of non-linearity, in the sense that its Hessians are non-zero along some direction, on a significant portion of the domain. Formally, we make the following definition:

In words, $\sigma_{\lambda}\left(f\right)$ is the measure (w.r.t. the uniform distribution on $\left[0,1\right]^{d}$) of the largest connected set in the domain of $f$, where at any point, $f$ has curvature at least $\lambda$ along some fixed direction $\mathbf{v}$. The “prototypical” functions $f$ we are interested in is when $\sigma_{\lambda}(f)$ is lower bounded by a constant (e.g. it is $1$ if $f$ is strongly convex). We stress that our results in this section will hold equally well by considering the condition $\mathbf{v}^{\top}H(f)(\mathbf{x})\mathbf{v}\leq-\lambda$ as well, however for the sake of simplicity we focus on the former condition appearing in Def. 1. Our goal is to show a depth separation result inidividually for any such function (that is, for any such function, there is a gap in the attainable error between deeper and shallower networks, even if the shallow network is considerably larger).

As usual, we start with an inapproximability result. Specifically, we prove the following lower bound on the attainable approximation error of $f$, using a ReLU neural network of a given depth and width:

The theorem conveys a key tradeoff between depth and width when approximating a $C^{2}$ function using ReLU networks: The error cannot decay faster than polynomially in the width $m$, yet the bound deteriorates exponentially in the depth $l$. As we show later on, this deterioration does not stem from the looseness in the bound: For well-behaved $f$, it is indeed possible to construct ReLU networks, where the approximation error decays exponentially with depth.

The proof of Thm. 4 appears in Subsection 6.3, and is based on a series of intermediate results. First, we show that any strictly curved function (in a sense similar to Definition 1) cannot be well-approximated in an $L_{2}$ sense by piecewise linear functions, unless the number of linear regions is large. To that end, we first establish some necessary tools based on Legendre polynomials. We then prove a result specific to the one-dimensional case, including an explicit lower bound if the target function is quadratic (Thm. 9) or strongly convex or concave (Thm. 10). We then expand the construction to get an error lower bound in general dimension $d$, depending on the number of linear regions in the approximating piecewise-linear function. Finally, we note that any ReLU network induces a piecewise-linear function, and bound the number of linear regions induced by a ReLU network of a given width and depth (using a lemma borrowed from Telgarsky (2016)). Combining this with the previous lower bound yields Thm. 4.

We now turn to complement this lower bound with an approximability result, showing that with more depth, a wide family of functions to which Thm. 4 applies can be approximated with exponentially high accuracy. Specifically, we consider functions which can be approximated using a moderate number of multiplications and additions, where the values of intermediate computations are bounded (for example, a special case is any function approximable by a moderately-sized Boolean circuit, or a polynomial).

The key result to show this is the following, which implies that the multiplication of two (bounded-size) numbers can be approximated by a ReLU network, with error decaying exponentially with depth:

The idea of the construction is that depth allows us to compute highly-oscillating functions, which can extract high-order bits from the binary representation of the inputs. Given these bits, one can compute the product by a procedure resembling long multiplication, as shown in Fig. 2, and formally proven as follows:

We begin by observing that by using a simple linear change of variables on $x$, we may assume without loss of generality that $x\in\left[0,1\right]$, as we can just rescale $x$ to the interval $\left[0,1\right]$, and then map it back to its original domain $\left[-M,M\right]$, where the error will multiply by a factor of $2M$. Then by requiring accuracy $\frac{\epsilon}{2M}$ instead of $\epsilon$, the result will follow.

The key behind the proof is that performing bit-wise operations on the first $k$ bits of $x\in\left[0,1\right]$ yields an estimation of the product to accuracy $2^{1-k}M$. Let $x=\sum_{i=1}^{\infty}2^{-i}x_{i}$ be the binary representation of $x$ where $x_{i}$ is the $i^{\text{th}}$ bit of $x$, then

Requiring that $2^{2-k}M\leq\frac{\epsilon}{2M}$, it suffices to show the existence of a network which approximates the function $\sum_{i=1}^{k}2^{-i}x_{i}\cdot y$ to accuracy $\frac{\epsilon}{2}$, where $k=2\left\lceil\log\left(\frac{8M}{\epsilon}\right)\right\rceil$. This way both approximations will be at most $\frac{\epsilon}{2}$, resulting in the desired accuracy of $\epsilon$.

Before specifying the architecture which extracts the $i^{\text{th}}$ bit of $x$, we first describe the last 2 layers of the network. Let the penultimate layer comprise of $k$ neurons, each receiving both $y$ and $x_{i}$ as input, and having the set of weights $\left(2^{-i},1,-1\right)$. Thus, the output of the $i^{\text{th}}$ neuron in the penultimate layer is

We now specify the architecture which extracts the first most significant $k$ bits of $x$. In Telgarsky (2016), the author demonstrates how the composition of the function

with itself $i$ times, $\varphi^{i}$, yields a highly oscillatory triangle wave function in the domain $\left[0,1\right]$. Furthermore, we observe that $\varphi\left(x\right)=0~{}\forall x\leq 0$, and thus $\varphi^{i}\left(x\right)=0~{}\forall x\leq 0$. Now, a linear shift of the input of $\varphi^{i}$ by $2^{-i-1}$, and composing the output with

We stress that choosing $\delta$ such that the network approximates the bit-wise product to accuracy $\frac{\epsilon}{2}$ will require $\delta$ to be of magnitude $\frac{1}{\epsilon}$, but this poses no problem as representing such a number requires $\log\left(\frac{1}{\epsilon}\right)$ bits, which is also the magnitude of the size of the network, as suggested by the following analysis.

Next, we compute the size of the network required to implement the above approximation. To compute $\varphi$ only two neurons are required, therefore $\varphi^{i}$ can be computed using $i$ layers with $2$ neurons in each, and finally composing this with $\sigma_{\delta}$ requires a subsequent layer with $2$ more neurons. To implement the $i^{\text{th}}$ bit extractor we therefore require a network of size $2\times\left(i+1\right)$. Using dummy neurons to propagate the $i^{\text{th}}$ bit for $i<k$, the architecture extracting the $k$ most significant bits of $x$ will be of size $2k\times\left(k+1\right)$. Adding the final component performing the multiplication estimation will require $2$ more layers of width $k$ and $1$ respectively, and an increase of the width by $1$ to propagate $y$ to the penultimate layer, resulting in a network of size $\left(2k+1\right)\times\left(k+1\right)$. ∎

Repeating these arguments, we see that any function which can be approximated by a bounded number of operations involving additions and multiplications, can also be approximated well by moderately-sized networks. This is formalized in the following theorem, which provides an approximation error upper bound (in the $L_{\infty}$ sense, which is stronger than $L_{2}$ for upper bounds):

As discussed in Sec. 2, this type of $L_{\infty}$ approximation bound implies an $L_{2}$ approximation bound with respect to any distribution. The proof of the theorem appears in Subsection 6.4.

Combining Thm. 4 and Thm. 6, we can state the following corollary, which formally shows how depth can be exponentially more valuable than width as a function of the target accuracy $\epsilon$:

Suppose $f\in C^{2}\cap\mathcal{F}_{t\left(\epsilon\right),M\left(\epsilon\right),\epsilon}$, where $t\left(\epsilon\right)=\mathcal{O}\left(\textnormal{poly}\left(\log\left(1/\epsilon\right)\right)\right)$ and $M\left(\epsilon\right)=\mathcal{O}\left(\textnormal{poly}\left(1/\epsilon\right)\right)$. Then approximating $f$ to accuracy $\epsilon$ in the $L_{2}$ norm using a fixed depth ReLU network requires width at least $\textnormal{poly}(1/\epsilon)$, whereas there exists a ReLU network of depth and width at most $p\left(\log\left(1/\epsilon\right)\right)$ which approximates $f$ to accuracy $\epsilon$ in the infinity norm, where $p$ is a polynomial depending solely on $f$.

The lower bound follows immediately from Thm. 4. For the upper bound, observe that Thm. 6 implies an $\epsilon$ approximation by a network of width and depth at most

which by the assumption of Corollary 1, can be bounded by

for some polynomial $p$ which depends solely on $f$. ∎

This research is supported in part by an FP7 Marie Curie CIG grant, Israel Science Foundation grant 425/13, and the Intel ICRI-CI Institute. We would like to thank Shai Shalev-Shwartz for some illuminating discussions, Eran Amar for his valuable help with the experiment, and Lv Xianzhang for spotting a mistake in a previous version of Sec. 3.

References

Proofs

This proof bears resemblance to the proof provided in Eldan & Shamir (2016)[Lemma 10], albeit once approximating $\left\|\mathbf{x}\right\|_{2}^{2}$, the following construction takes a slightly different route. For completeness, we also state assumption 1 from Eldan & Shamir (2016):

As discussed in Eldan & Shamir (2016), this assumption is satisfied by ReLU, sigmoid, threshold, and more generally all standard activation functions we are familiar with.

which is constant outside $\left[-1,1\right]$, as well as the function

and where the width parameter $w$ is at most $\frac{c_{\sigma}d}{\delta_{1}}$. Consequently, the function

can be expressed in the form $a+\sum_{i=1}^{w}\alpha_{i}\sigma\left(\beta_{i}x-\gamma_{i}\right)$ where $w\leq\frac{c_{\sigma}d^{2}}{\delta_{1}}$, yielding an approximation satisfying

We now invoke assumption 1 again to approximate the $1$-Lipschitz function

for appropriate scalars $a,u_{i},c_{i},v_{i,j},b_{i,j}$ and vectors $\mathbf{w}_{i,j}$, and where $w$ is at most $\max\left\{c_{\sigma}d^{2}/\delta_{1},c_{\sigma}/2\delta_{2}\right\}$. It is now left to bound the approximation error obtained by $g$. We have

Beginning with the second summand, define for any $\epsilon>0$,

Since $\mu$ is continuous, there exists $\epsilon\in(0,1)$ such that

Combining both Eq. (10) and Eq. (11) we compute

where the equality is since both functions are equal outside of $R_{\epsilon}$, the first inequality is since the difference between the two functions on $R_{\epsilon}$ is at most $1$, and the last inequality is due to Eq. (9). Moving to the first summand in Eq. (8), we have

where the third inequality is due to Eq. (7) and $f$ being $1$-Lipschitz and the last inequality due to Eq. (6). Letting $\delta_{2}=\sqrt{\delta}/4$ and $\delta_{1}=\sqrt{\delta}/4c_{\mu}$ which also entails $w\leq\frac{2c_{\sigma}}{\sqrt{\delta}}\cdot\max\left\{2c_{\mu}d^{2},1\right\}$, the above is upper bounded by $\sqrt{\delta}/2$, which when combined with Eq. (12) and plugged in Eq. (8) implies the lemma. ∎

2 Proof of Thm. 3

Consider an input distribution of the form

where $\mathbf{v}$ is drawn from a certain distribution on the unit $L_{1}$ sphere $\{\mathbf{x}:\left\|\mathbf{x}\right\|_{1}=1\}$ to be specified later, and $s$ is uniformly distributed on $[1,1+\epsilon]$.

be a 2-layer ReLU network of width $N$, such that with respect to the distribution above,

where in the first inequality we used the fact that $\frac{1}{1+\epsilon}\geq 1-\epsilon$ for all $\epsilon\in(0,1)$, and in the second inequality we used a union bound. Combining these inequalities with Eq. (13), we get that

As a result, to prove the theorem, it is enough to construct a distribution for $\mathbf{v}$ on the on the unit $L_{1}$ ball, such that for any $\mathbf{w}$,

where $c_{d}>0$ is a parameter dependent on $d$ to be determined later. It is easily verified that $\left\langle\boldsymbol{\sigma}/d,\hat{\mathbf{v}}\right\rangle=\left\langle\boldsymbol{\sigma}/d,\boldsymbol{\sigma}/d\right\rangle$ independent of $\mathbf{n}$, hence $\hat{\mathbf{v}}$ lies on the hyperplane containing the facet of the $L_{1}$ ball on which $\boldsymbol{\sigma}/d$ resides. Calling this facet $F_{\boldsymbol{\sigma}}$, we define $\mathbf{v}$ to have the same distribution as $\hat{\mathbf{v}}$, conditioned on $\hat{\mathbf{v}}\in F_{\boldsymbol{\sigma}}$.

To see this, let $A=\{\mathbf{x}:\left\langle\mathbf{w},\mathbf{x}\right\rangle\in[1-\epsilon,1]\}$, and note that the left hand side equals

Therefore, to prove Eq. (15), it is enough to prove that $\Pr(\hat{\mathbf{v}}\in F_{\boldsymbol{\sigma}}|\boldsymbol{\sigma})\geq 1/2$ for any $\boldsymbol{\sigma}$. As shown earlier, $\hat{\mathbf{v}}$ lies on the hyperplane containing $F_{\boldsymbol{\sigma}}$, the facet of the $L_{1}$ ball in which $\boldsymbol{\sigma}/d$ resides. Thus, $\hat{\mathbf{v}}$ can be outside $F_{\boldsymbol{\sigma}}$, only if at least one of its coordinates has a different sign than $\boldsymbol{\sigma}$. By definition of $\hat{\mathbf{v}}$, this can only happen if $\left\|c_{d}(I-\boldsymbol{\sigma}\boldsymbol{\sigma}^{\top}/d)\mathbf{n}\right\|_{\infty}\geq 1$. The probability of this event (over the random draw of $\mathbf{n}$) equals

Since $\sigma_{i}\in\{-1,1\}$ for all $i$, the event on the right hand side can only occur if $|n_{j}|\geq 1/2c_{d}$ for some $j$. Recalling that each $n_{j}$ has a standard Gaussian distribution, this probability can be upper bounded by

where we used a union bound and a standard Gaussian tail bound. Thus, by picking

we can ensure that the probability is at most $1/2$, hence proving that $\Pr(\hat{\mathbf{v}}\in F_{\boldsymbol{\sigma}}|\boldsymbol{\sigma})\geq 1/2$ and validating Eq. (15).

With Eq. (15) in hand, we now turn to upper bound

By the equation above, we have that conditioned on $\boldsymbol{\sigma}$, the distribution of $\left\langle\mathbf{w},\hat{\mathbf{v}}\right\rangle$ is Gaussian with mean $\left\langle\boldsymbol{\sigma},\mathbf{w}\right\rangle/d$ and variance

By Hoeffding’s inequality, we have that for any $t>0$,

This means that with probability at least $1-2\exp(-d)-2\exp(-2t^{2})$ over the choice of $\boldsymbol{\sigma}$, the distribution of $\left\langle\mathbf{w},\hat{\mathbf{v}}\right\rangle$ (conditioned on $\boldsymbol{\sigma}$) is Gaussian with mean bounded in absolute value by $t\left\|\mathbf{w}\right\|/d$, and variance of at least $\left(\frac{c_{d}\left\|\mathbf{w}\right\|}{d}\right)^{2}\cdot\left(1-\frac{1}{d}\cdot\frac{d}{2}\right)=\frac{1}{2}\left(\frac{c_{d}\left\|\mathbf{w}\right\|}{d}\right)^{2}$. To continue, we utilize the following lemma:

Since the probability can only increase if we replace the mean $\mu$ by $|\mu|$, we will assume without loss of generality that $\mu\geq 0$.

By definition of a Gaussian distribution, and using the easily-verified fact that $\exp(-z^{2})\leq\min\{1,1/z\}$ for all $z\geq 0$, the probability equals

A simple case analysis reveals that the denominator is at leastIf $\mu\in[1-\epsilon,1]$, then we get $\max\{\mu,0\}=\mu\geq 1-\epsilon$. If $\mu>1$, we get $\max\{\mu,\mu-1\}>1\geq 1-\epsilon$. If $\mu<1-\epsilon$, we get $\max\{\mu,1-\epsilon-\mu\}\geq(1-\epsilon)/2$. $\frac{1-\epsilon}{2}$, from which the result follows. ∎

Using this lemma and the previous observations, we get that with probability at least $1-2\exp(-d)-2\exp(-2t^{2})$ over the choice of $\boldsymbol{\sigma}$,

Letting $E$ be the event that $\boldsymbol{\sigma}$ is such that this inequality is satisfied (and noting that its probability of non-occurence is at most $2\exp(-d)+2\exp(-2t^{2})$), we get overall that

Recalling Eq. (15) and the definition of $c_{d}$, we get that

Picking $t=\sqrt{\frac{1}{2}\log\left(\frac{1-\epsilon}{\epsilon}\right)}$, we get the bound

This justifies Eq. (14), from which the result follows.

3 Proof of Thm. 4

The proof rests largely on the following key result:

Before proving Thm. 7, let us explain how we can use it to prove Thm. 4. To that end, we use the result in Telgarsky (2016, Lemma 3.2), of which the following is an immediate corollary:

Let $\mathcal{N}_{m,l}^{d}$ denote the family of ReLU neural networks receiving input of dimension $d$ and having depth $l$ and maximal width $m$. Then

Combining this corollary with Thm. 7, the result follows. The remainder of this subsection will be devoted to proving Thm. 7.

Let $P_{i}$ denote the $i^{\text{th}}$ Legendre Polynomial given by Rodrigues’ formula:

These polynomials are useful for the following analysis since they obey the orthogonality relationship

The shifted Legendre polynomials obey the orthogonality relationship

A generalization of Parseval’s identity yields

A function $f$ is $\lambda$-strongly convex if for all $\mathbf{w},\mathbf{u}$ and $\alpha\in(0,1)$,

A function is $\lambda$-strongly concave, if $-f$ is $\lambda$-strongly convex.

3.2 One-dimensional Lower Bounds

We begin by proving two useful lemmas; the first will allow us to compute the error of a linear approximation of one-dimensional functions on arbitrary intervals, and the second will allow us to infer bounds on the entire domain of approximation, from the lower bounds we have on small intervals where the approximating function is linear.

Where in the second equality we used the orthogonality relationship from Eq. (17), and the generalized Parseval’s identity from Eq. (18). ∎

Now, recall Hölder’s sum inequality which states that for any $p,q$ satisfying $\frac{1}{p}+\frac{1}{q}=1$ we have

Plugging the inequality from Eq. (21) with $p=5$ in Eq. (20) yields

Our first lower bound for approximation using piece-wise linear functions is for non-linear target functions of the simplest kind. Namely, we obtain lower bounds on quadratic functions.

If $\mathcal{G}_{n}$ is the family of piece-wise linear functions with at most $n$ linear segments in the interval $\left[0,1\right]$, then for any quadratic function $p(x)=p_{2}x^{2}+p_{1}x+p_{0}$, we have

Note that for quadratic functions, the optimal error is dependent solely on the length of the interval. Using Lemma 3 with $c=\frac{p_{2}^{2}}{180}$ we get

For non-quadratic functions, however, we now show that a lower bound can be derived under the assumption of strong convexity (or strong concavity) in $\left[0,1\right]$.

We first stress that an analogous assumption to $\lambda$-strong convexity would be that $f$ is $\lambda$-strongly concave, since the same bound can be derived under concavity by simply applying the theorem to the additive inverse of $f$, and observing that the additive inverse of any piece-wise linear approximation of $f$ is in itself, of course, a piece-wise linear function. For this reason from now on we shall use the convexity assumption, but will also refer without loss of generality to concave functions.

We now integrate by parts twice, taking the anti-derivative of the polynomial to obtain

But since $\frac{t^{2}}{2}-\frac{t^{4}}{4}\in\left[0,\frac{1}{4}\right]~{}\forall t\in\left[-1,1\right]$ and since $f^{\prime\prime}>0$ due to strong convexity, we have that

Plugging this inequality in Eq. (24) yields

and by using the strong convexity of $f$ again, we get that

First, observe that if $f$ is $\lambda$-strongly convex on $\left[a,b\right]$, then $f\left(\left(b-a\right)x+a\right)$ is $\lambda\left(b-a\right)^{2}$-strongly convex on $\left[0,1\right]$ since $\forall x\in\left[0,1\right]$,

Now, we use the change of variables $x=\left(b-a\right)t+a$, $dx=\left(b-a\right)dt$

where the inequality follows from an application of Thm. 10. Back to the theorem statement, if $\sigma_{\lambda}=0$ then the bound trivially holds, therefore assume $\lambda>0$ such that $\sigma_{\lambda}>0$. Since $f$ is strongly convex on a set of measure $\sigma_{\lambda}>0$, the theorem follows by applying the inequality from Eq. (6.3.2). ∎

3.3 Multi-dimensional Lower Bounds

We now move to generalize the bounds in the previous subsection to general dimension $d$. Namely, we can now turn to proving Thm. 7.

Analogously to the proof of Thm. 11, we identify a neighborhood of $f$ in which the restriction of $f$ to a line in a certain direction is non-linear. We then integrate along all lines in that direction and use the result of Thm. 11 to establish the lower bound.

We now integrate the approximation error on $f$ in the neighborhood $U$ along the direction $\mathbf{v}$. Compute

where in the second inequality we used Thm. 11 and in the third inequality we used Jensen‘s inequality with respect to the convex function $x\mapsto\left|x\right|^{5}$. ∎

4 Proof of Thm. 6

and for multiplication we compute the product error estimation

From this, we see that at each stage the error grows by at most a multiplicative factor of $3M$. After $t$ operations, and with an initial estimation error of $\delta$, we have that the error is bounded by $\left(3M\right)^{t-1}\delta$. Choosing $\delta\leq\left(3M\right)^{1-t}\epsilon$ to guarantee approximation $\epsilon$, we have from Thm. 5 that each operation will require at most

depth for some universal $c>0$. Composing the networks performing each operation, we arrive at a total network width and depth of at most

Now, our target function is approximated to accuracy $\epsilon$ by a function which our network approximates to the same accuracy $\epsilon$, for a total approximation error of the target function by our network of $2\epsilon$.