Expressivity of Shallow and Deep Neural Networks for Polynomial
  Approximation
This study explores the number of neurons required for a Rectified Linear
Unit (ReLU) neural network to approximate multivariate monomials. We establish
an exponential lower bound on the complexity of any shallow network
approximating the product function over a general compact domain. We also
demonstrate this lower bound doesn't apply to normalized Lipschitz monomials
over the unit cube. These findings suggest that shallow ReLU networks
experience the curse of dimensionality when expressing functions with a
Lipschitz parameter scaling with the dimension of the input, and that the
expressive power of neural networks is more dependent on their depth rather
than overall complexity.
Itai Shapira
# Expressivity of Shallow and Deep Neural Networks for Polynomial Approximation

###### Abstract

We delve into the required number of neurons for a Rectified Linear Unit (ReLU) neural network to approximate multivariate monomials. Our investigation establishes an exponential lower bound on the complexity of any shallow network approximating the product function \(\textbf{x}\mapsto\prod_{i=1}^{d}x_{i}\) over a general compact domain. Moreover, we demonstrate this lower bound does not apply to normalized \(\mathcal{O}(1)\)-Lipschitz monomials (or equivalently, by restricting to the unit cube). These results suggest that shallow ReLU networks suffer from the curse of dimensionality when expressing functions with a Lipschitz parameter scaling with the dimension of the input, and that the expressive power of neural networks lies in their depth rather than the overall complexity.

## 1 Introduction

Shallow neural networks, and by extension multi-hidden layer networks, are universal approximators. For every continuous non-polynomial activation function, the space of all shallow one-hidden layer networks is dense in \(C(K)\) in the uniform topology, for any compact \(K\subset\mathbb{R}^{d}\)(Pinkus (1999)). Density, however, does not imply an efficient scheme for approximation, namely the required number of neurons and trainable parameters. Indeed, the minimum number of neurons required to \(\varepsilon\)-approximate a large class of functions can be exponential in the dimension of the input. Specifically, for the unit ball of the Sobolev space of order \(r\) and dimension \(d\), Maiorov et al. (1999) show a lower bound of order \(\mathcal{O}(\varepsilon^{-\frac{d-1}{r}})\) and that the set of functions for which this lower bound holds is of large measure.

This lower bound reflects the so-called curse of dimensionality: the number of computational units necessary for approximation scales exponentially with the problem dimension. In this regard, shallow networks offer no superior order of approximation compared to other functional approximation schemes, such as polynomial approximation (Pinkus (1999)).

In contrast, _deep_ networks featuring multiple hidden layers have proven effective in high-dimensional applications such as image recognition and natural language processing. In light of this empirical success, numerous studies have examined the approximation capabilities of deep versus shallow networks. It has been suggested that the expressive power of neural networks is attributed to their depth. When compared to shallow networks of equivalent size, deeper networks may offer greater expressivity and can efficiently capture functions that would demand exponentially-wide shallow networks (refer to section 3 for a review). Possibly the most striking illustration of this is the _depth separation phenomena_: studies such as Eldan and Shamir (2016); Safran and Shamir (2017); Daniely (2017), and Venturi et al. (2021) demonstrate that certain functions can be efficiently represented using depth two networks, yet require exponentially wider networks for approximation by shallow, one-hidden-layer networks.

A particularly interesting case study for the complexity gap between deep and shallow neural networks involves the class of homogeneous multivariate polynomials of \(d\) variables, represented by
the monomials:

\[p_{d}(x_{1},..,x_{d}):=\prod_{i=1}^{d}x_{i}\]

i.e. the \(d\)-product function. Deep networks can approximate \(p_{d}\) efficiently. Monomials are _compositionally sparse_, implying they can be expressed by recursive compositions of the low-dimension function \((x,y)\mapsto xy\). Consequently, a tree-like network architecture with \(\log d\) layers can approximate \(p_{d}\) with a linear number of neurons (Mhaskar et al. (2016); Poggio et al. (2017)). This result prompts the following question:

_Can an \(\mathcal{O}(1)\)-layer network approximate \(\textbf{x}\mapsto\prod_{i=1}^{d}x_{i}\) over a general compact domain \([-k,k]^{d}\) with only \(\text{poly}(d)\) neurons?_

Lin et al. (2017) and Rolnick and Tegmark (2017) studied this problem in the context of _exact approximation_, that is, how many neurons are necessary to have the property that for any precision \(\varepsilon>0\), there exists a weight assignment that approximate \(p_{d}\). For this notion of approximation, they demonstrated that an exponential number of neurons is needed for a shallow network with a smooth activation function. However, it remained uncertain whether a smaller network could be constructed to approximate \(p_{d}\) arbitrarily well in the standard notion of approximation, where the number of neurons is allowed to vary with the level of accuracy \(\varepsilon\).

Blanchard and Bennouna (2021) recently constructed a two-layer ReLU network with \(\text{poly}(d)\) neurons that approximates the product function over \([0,1]^{d}\). This corresponds to the normalized monomial \(\textbf{x}\mapsto\frac{1}{k^{d}}\prod_{i=1}^{d}x_{i}\) over \([0,k]^{d}\), where \(k\) is a constant. However, we demonstrate that the choice of approximation domain \([0,1]^{d}\) (or equivalently, the normalization factor \(k^{-d}\)) hides a gap between the positive and negative answers to the question of the expressive power of ReLU networks in the context of homogeneous polynomials.

In this paper, we offer a characterization of the expressive power of ReLU networks for homogeneous polynomials. We demonstrate that over the domain \((1,k]^{d}\), the product function acts as an expansive map with an expansion constant that scales exponentially with the dimension. As a result, we prove that no \(\mathcal{O}(1)\)-layer ReLU network exists that can approximate \(p_{d}\) with at most \(\text{poly}(d)\) neurons. Conversely, for the normalized case where the Lipschitz parameter is independent of the dimension, we extend the result of Blanchard and Bennouna (2021). We show that \(p_{d}\) can be efficiently approximated by a one-hidden-layer shallow network with a smooth or ReLU activation function. In particular, we reveal that no depth separation exists between one- and two-hidden-layer networks when approximating the class of homogeneous polynomials.

Our main contributions can be summarized as follows:

* In Section 4, we demonstrate that the minimum number of neurons required by any ReLU \(\mathcal{O}(1)\)-layer network to approximate multivariate monomials **scales exponentially with the dimension** over \([-k,k]^{d}\) with \(k>1\). More specifically, we prove the following theorem: **Theorem 1**.: _If a ReLU network with \(L\) layers and at most \(n\) neurons in each layer \(\varepsilon\)-approximates \(\textbf{x}\mapsto\prod_{i=1}^{d}x_{i}\) over \([-k,k]^{d}\) for \(k>1\), then \(n=\exp(\mathcal{O}(\frac{d}{L}\ln(\varepsilon^{-1})))\). (See Theorem 3 for a formal statement)_
* In Section 5, we demonstrate that the normalized monomial \(\textbf{x}\mapsto k^{-d}\prod_{i=1}^{d}x_{i}\) over \([0,k]^{d}\) (equivalently, \(p_{d}\) over \([0,1]^{d}\)) can be **approximated using a one-hidden layer ReLU network with \(\text{poly}(d)\) neurons**

## 2 Preliminaries

### Feedforward Neural Networks

Let \(K\subset\mathbb{R}^{d}\) be a compact set and \((C(K),||\cdot||_{\infty})\) denote the space of all continuous functions on \(K\), equipped with the uniform norm: \(||f||=\max_{x\in K}|f(x)|\). In this work, we contemplate the standard model of feedforward neural networks, using linear output neurons and a non-linear
continuous activation function \(\sigma:\mathbb{R}\longrightarrow\mathbb{R}\) for the other neurons. Following the notation in Pinkus (1999), we denote by \(\mathcal{M}^{1}_{n}(\sigma)\) the set of all 1-hidden layer neural networks:

\[\mathcal{M}^{1}_{n}(\sigma)=\bigg{\{}\sum_{i=1}^{n}\nu_{i}\sigma(\textbf{w}_{i} ^{T}\textbf{x}+b_{i})\mid\nu_{i},b_{i}\in\mathbb{R},\textbf{w}_{i}\in\mathbb{R} ^{d}\bigg{\}}\]

Throughout this work, we adopt the convention of referring to \(f\in\mathcal{M}^{1}_{n}(\sigma)\) as _shallow networks_. For brevity, we also employ matrix notation \(\mathcal{M}^{1}_{n}(\sigma)=\textbf{A}_{1}\sigma(\textbf{A}_{0}\textbf{x}+ \textbf{b}_{0})\), where \(\textbf{A}_{0}\) is an \(n\times d\) matrix, \(\textbf{A}_{1}\) is a \(1\times n\) matrix and \(\sigma\) is applied element-wise to vectors. The total number of trainable parameters is \((d+2)n\). A deep neural network with \(L\) hidden layers is obtained by feeding the outputs of a given layer as inputs to the next:

\[\mathcal{M}^{L}_{n}(\sigma)=\bigg{\{}\textbf{A}_{L}(\sigma\cdots\sigma( \textbf{A}_{1}(\sigma(\textbf{A}_{0}\textbf{x}+\textbf{b}_{0}))+\textbf{b}_{1 })\cdots)\bigg{\}}\]

where \(n\) is the maximum number of neurons in each hidden layer. The constant \(L\) is referred to as the _depth_ of the network.

We will consider two types of activation functions: piece-wise linear activation, such as the popular rectified linear unit (ReLU) \(\sigma(x):=\max\{x,0\}\); and general smooth non-polynomial activation functions, such as the exponential function \(\exp(x):=e^{x}\).

### Approximation Complexity

We will consider \(L^{\infty}\)-error of approximation. We say that a network \(g\in\mathcal{M}^{L}_{n}(\sigma)\)\(\varepsilon\)-approximates a function \(f\) if \(||f-g||<\varepsilon\) in the uniform topology. We measure the complexity of the network by the number of neurons and non-zero weights in the network. We are interested in evaluating the number of neurons needed to approximate a given function within \(\varepsilon\), and especially how this number scales with the dimension of the problem \(d\) and with the accuracy level \(\varepsilon\).

Roughly speaking, we consider shallow networks to be inefficient in approximating a sequence of functions \((f_{d}:\mathbb{R}^{d}\longrightarrow\mathbb{R})_{d\in\mathbb{N}}\), if the minimum number of neurons needed to \(\varepsilon\)-approximate the sequence grows exponentially with \(d\). Conversely, for any fixed \(\varepsilon\), polynomial dependency on \(d\) is considered efficient. Note, however, that we do not require a polynomial dependence on \(\varepsilon^{-1}\) and \(d\) simultaneously. For the remainder of the paper, we will use \(\mathcal{O}\) notation which hides constants independent of \(d\).

## 3 Related Work

**Slow approximation by shallow networks in standard function spaces.** Several studies have shown that shallow networks are inefficient in approximating Sobolev functions. Maiorov et al. (1999) consider the rate of approximation by arbitrary ridge functions. They show a lower bound that scales exponentially with \(d\), thus demonstrating the inherent inefficiency of _any_ shallow-like approximation schemes. DeVore et al. (1989) proved that any continuous function approximator that \(\varepsilon\)-approximates functions from the unit ball in the Sobolev space of order \(r\) and dimension \(d\) needs at least \(\Theta(\varepsilon^{-\frac{d}{r}})\) parameters (note, however, that the optimal weight selection is generally not continuous). Pinkus (1999) and Yarotsky (2017) prove the existence of norm-one Sobolev functions that cannot be approximated efficiently by shallow network, for smooth and ReLU activation functions, respectively.

**Faster approximation by deep networks.** Several studies have shown that deeper networks perform better for a given number of neurons. This indicates that the expressive power of neural networks lies in their depth rather than the overall complexity. Telgarsky (2015) show a \(k\)-layer \(\mathcal{O}(1)\)-wide 1-dimensional ReLU network which oscillates \(\mathcal{O}(2^{k})\) times that cannot be approximated by a \(k\)-polynomial shallow network. Yarotsky (2017) show every \(f\in C^{2}([0,1]^{d})\) cannot be \(\varepsilon\)-approximated by a \(L\)-deep ReLU network with fewer than \(\mathcal{O}(\varepsilon^{-\frac{1}{2L}})\) neurons, demonstrating the efficiency of increased depth. Mhaskar et al. (2016) and Poggio et al. (2017) show that deep neural networks can efficiently express _compositionally sparse_ functions, i.e. functions that can be expressed by recursive compositions of low-dimension functions. Other authors considered the power of deeper networks of different types. The exponential benefit of depth was shown
by Delalleau and Bengio (2011) (networks consisting of sum and product nodes) and Cohen et al. (2016) (convolutional arithmetic circuit architecture that incorporates locality, sharing, and pooling).

**Separation gaps.** Several works have studied the gap in expressivity between one-hidden-layer and two-hidden-layer networks, and have proved the existence of functions that can be efficiently approximated by two-hidden-layer networks, but require exponential width shallow networks. Eldan and Shamir (2016) prove a separation gap for rapidly oscillating radial functions using ReLU networks. Similar separation gaps have been shown by Daniely (2017); Safran and Shamir (2017); Venturi et al. (2021).

**Flattening results.** Recent work studied the complexity cost of flattening deep networks into shallow ones. Safran et al. (2019) discuss flattening networks which approximate \(\mathcal{O}(1)\)-Lipschitz radial functions. Venturi et al. (2021) show that functions with an \(\mathcal{O}(1)\)-rate of oscillation can be approximated by one-hidden-layer networks.

**Approximation of the product function.** The product function is a special case of compositionally-sparse functions and thus can be approximated by deep networks, as shown in Mhaskar et al. (2016) and Poggio et al. (2017). Lin et al. (2017) and Rolnick and Tegmark (2017) studied the _exact_-approximation capabilities of shallow and deep networks in approximating this function. They proved that if \(m(\varepsilon)\) is the minimum number of neurons required by a smooth shallow network to \(\varepsilon\)-approximate \(p_{d}\), then \(\lim_{\varepsilon\to 0}m(\varepsilon)\) exists and equals to \(2^{d}\) (In Appendix B, we attached a slightly shorter proof). More recently, Blanchard and Bennouna (2021) constructed a two-hidden-layer ReLU architecture that \(\varepsilon\)-approximates the normalized \(p_{d}\) with \(\mathcal{O}(d^{\frac{3}{2}}\varepsilon^{-\frac{1}{2}}\ln\varepsilon^{-1})\) neurons.

## 4 The Inefficiency of Shallow Network on a General Compact Domain

In this section we provide an exponential lower bound on the complexity of a ReLU network that \(\varepsilon\)-approximate the multivariate monomial by counting the number of linear regions in which the network is linear.

Shallow networks with a piecewise linear activation function compute piecewise linear functions. ReLU activation functions, of the form \(\max\{\textbf{w}^{T}\textbf{x}+b,0\}\), operate in one of two modes - they either output \(0\) or a linear function of the input. The boundary between these two behaviors is the hyperplane \(H=\{\textbf{x}\mid\textbf{w}^{T}\textbf{x}+b=0\}\) which splits the input space \(\mathbb{R}^{d}\) into two pieces. A shallow network with \(n\) neurons forms an \(d\)-dimensional _hyperplane arrangement_\(\{H_{i}\subset\mathbb{R}^{d}\}_{i\in[n]}\). A _linear region_ of an arrangement is a connected component of \(\mathbb{R}^{d}\setminus\bigcup_{i\in[n]}H_{i}\)(Pascanu et al. (2013)). In every such region, the inference function of the network is affine linear.

An arbitrary non-linear function, when defined on a sufficiently large set, cannot be approximated by linear functions. For the sake of building intuition for the below result, consider the following example inspired by Liang and Srikant (2016) (Theorem 11). Suppose that \(f:\mathbb{R}^{d}\longrightarrow\mathbb{R}\) is strongly-convex with parameter \(m>0\) and \(T\) is a linear function that \(\varepsilon\)-approximates \(f\) over the domain \(K\). Then the error function \(g(x):=f(x)-T(x)\) is also strongly convex. If \(\textbf{x}_{0}\in\mathbb{R}^{d}\) is any point with \(\nabla g(\textbf{x}_{0})=0\), then by definition:

\[2\varepsilon>g(\textbf{y})-g(\textbf{x}_{0})=\frac{m}{2}||\textbf{y}-\textbf{x }_{0}||_{2}^{2}\]

that is, in order for \(T\) to \(\varepsilon\)-approximates \(f\), the domain \(K\) must have a relatively small diameter. By finding an upper bound on the number of linear regions generated by the network, we can derive a lower bound on the number of neurons required to approximate a general (not necessarily strongly convex) function \(f\).

The topic of counting the number of linear regions generated by a ReLU network has been addressed by several authors (Montufar et al. (2014);Telgarsky (2015);Pascanu et al. (2013). See also Zaslavsky (1975)). The function represented by the network can have a number of linear pieces that is exponential in the number of layers, but is at most polynomial in the number of neurons (Hanin and Rolnick (2019)). An upper bound for the case of \(d=1\) is given by Telgarsky (2015) (see also Yarotsky (2017) (Lemma 4)):
**Lemma 2** (Telgarsky (2015) (Lemma 2.1)).: _Consider \(f\in\mathcal{M}_{n}^{L}(\sigma)\), a \(1\)-dimensional ReLU network with \(L\) hidden layers and no more than \(n\) neurons in each hidden layer. The number of linear pieces in \(f\) is at most \((2n)^{L}\)._

Using Lemma 2, we can now prove the main result of this section:

**Theorem 3**.: _If \(k>1\) and \(\varepsilon>0\), then any network \(f\in\mathcal{M}_{n}^{L}(\text{ReLU})\) that \(\varepsilon\)-approximates the univariate monomial \(p_{d}(x)=\prod_{i=1}^{d}x_{i}\) on \(K:=[-k,k]^{d}\), must satisfy \(n>C_{1}\varepsilon^{-\frac{1}{2L}}d^{\frac{1}{2L}}\exp(C_{2}\frac{d}{L})\), where \(C_{1},C_{2}>0\) are constants independent of \(d\) and \(\varepsilon\). Specifically, \(n\) must scale exponentially with \(d\)._

Proof.: The shallow network \(f\)\(\varepsilon\)-approximates \(p_{d}\) in \(K\) and, in particular, approximates \(p\) along the direction \(\lambda(1,1,..,1)\). We define \(\tilde{p}_{d},\tilde{f}:[\frac{k+1}{2},k]\longrightarrow\mathbb{R}\) as the restrictions of \(p_{d}\) and \(f\) respectively along this direction:

\[\tilde{f}(x)=f(x,...,x)\quad\tilde{p}_{d}(x)=x^{d}\]

clearly \(|\tilde{f}(x)-\tilde{p}_{d}(x)|<\varepsilon\) for every \(x\in[\frac{k+1}{2},k]\). Additionally, \(\tilde{f}\) is a univariate shallow network with \(n\) neurons, obtainable from \(f\) by replacing the \(d\) input units with one input and modify the connection accordingly.

\(\tilde{f}\) is a continuous piece-wise affine linear function with \((2n)^{L}\) linear pieces. Therefore, the domain \([\frac{k+1}{2},k]\) is partitioned into at most \((2n)^{L}\) intervals for which \(\tilde{f}\) is linear. Hence, there exists an interval \([a,b]\subset[\frac{k+1}{2},k]\) with \(b-a\geq\frac{k-1}{2(2n)^{L}}\) such that \(\tilde{f}\) is linear on \([a,b]\) and \(\varepsilon\)-approximates \(x^{d}\). Denote by \(\tilde{h}\) the error function \(\tilde{h}:=(\tilde{p}_{d}(x)-\tilde{f}(x))\). Notice that: \(|\tilde{h}(x)|<\varepsilon\) for all \(x\in[a,b]\).

Consider the following three points \(a,b\) and \(\frac{a+b}{2}\in[a,b]\). It follows from the linearity of \(\tilde{f}\):

\[\begin{split} 4\varepsilon>\tilde{h}(b)+\tilde{h}(a)-2\tilde{h}( \frac{a+b}{2})&=\left(\tilde{p}_{d}(b)-\tilde{p}_{d}(\frac{a+b}{ 2})\right)+\left(\tilde{p}_{d}(a)-\tilde{p}_{d}(\frac{a+b}{2})\right)\\ &+\left(\tilde{f}(\frac{a+b}{2})-\tilde{f}(b)\right)+\left(\tilde {f}(\frac{a+b}{2})-\tilde{f}(a)\right)\\ &=\left(\tilde{p}_{d}(b)-\tilde{p}_{d}(\frac{a+b}{2})\right)+ \left(\tilde{p}_{d}(a)-\tilde{p}_{d}(\frac{a+b}{2})\right)\end{split} \tag{1}\]

Notice that on \([\frac{K+1}{2},K]\), the function \(\tilde{p}_{d}\) is strongly convex with parameter \(m:=d(d-1)(\frac{k+1}{2})^{d-2}\). It follows than:

\[\tilde{p}_{d}(b)+\tilde{p}_{d}(a)-2\tilde{p}_{d}(\frac{a+b}{2})\geq\frac{m}{ 4}(b-a)^{2}\]

It follows that: \(4\varepsilon>\frac{m}{4}(b-a)^{2}\) and using the fact that \(b-a\geq\frac{k-1}{2(2n)^{L}}\):

\[4\varepsilon>\frac{d(d-1)}{16}(\frac{k+1}{2})^{d-2}(k-1)^{2}(2n)^{-2L}\]

that is, exists \(C_{1},C_{2}>0\) independent of \(d\) and \(\varepsilon\) with: \(n>C_{1}\varepsilon^{-\frac{1}{2L}}d^{\frac{1}{2L}}\exp(C_{2}\frac{d}{L})\).

## Discussion

Theorem 3 tells us that \(\varepsilon\)-approximating the product function outside the unit cube requires exponentially wide \(\mathcal{O}(1)\)-deep ReLU networks. The proof relies on the fact that \(\textbf{x}\mapsto\prod_{i=1}^{d}x_{i}\) is expansive, with an expansion factor that scales exponentially with \(d\). In contrast, over \([0,1]^{d}\), \(p_{d}\) is \(1\)-Lipschitz, and this Lipschitz parameter does not scale with \(d\). Note that expressing \(p_{d}\) over this domain is equivalent to approximate the _normalized monomial_:

\[\textbf{x}\in[0,k]^{d}\mapsto\frac{1}{k^{d}}\prod_{i=1}^{d}x_{i} \tag{2}\]

Recently, Blanchard and Bennouna (2021) showed the following:
**Theorem 4** (Blanchard and Bennouna (2021), Proposition 3.2).: _For all \(\varepsilon>0\), there exists a two-hidden-layer ReLU network with \(\text{poly}(d)\) neurons that \(\varepsilon\)-approximates \(\textbf{x}\in[0,1]^{d}\mapsto\prod_{i=1}^{d}x_{i}\)_

Together, Theorems 3 and 4 suggest that the curse of dimensionality of shallow ReLU networks is closely related to the derivative of the objective function and how its magnitude scales with the dimension. Analogously, in a seminal work, Eldan and Shamir (2016) and Safran et al. (2019) investigated radial functions of the form \(f(\textbf{x})=\varphi(||\textbf{x}||)\). The former demonstrated that no one-hidden layer network can approximate \(f\) if \(\varphi\) is rapidly oscillating, with a Lipschitz parameter scaling polynomially with \(d\). Meanwhile, the latter established that if \(\varphi\) is \(\mathcal{O}(1)\)-Lipschitz, approximation by a shallow network is feasible with \(\text{poly}(d)\) neurons. In our framework, the proof of 4 relies on the observation that \(p_{d}(\textbf{x})=\exp(\sum_{i=1}^{d}\ln x_{i})\) and that \(\exp\) is \(\mathcal{O}(1)\)-Lipschitz if \(x_{i}\leq 1\).

## 5 Fast Approximation Using Shallow Networks For Normalized Monomials

Extending the findings of Blanchard and Bennouna (2021), in this section we raise the following question:

_Is there a depth separation between one and two-hidden-layer networks in the approximation of the normalized monomial?_

In other words, does a shallow counterpart to Theorem 4 with \(\text{poly}(d)\) number of neurons exist? In the following theorem, we address this question by constructing a shallow ReLU network with \(\text{poly}(d)\) number of neurons that \(\varepsilon\)-approximates the normalized \(p_{d}\).

**Theorem 5**.: _Let \(k>0\). For any \(\varepsilon>0\), there exists a shallow network \(\hat{f}\in\mathcal{M}^{1}_{n}(\text{ReLU})\) that \(\varepsilon\)-approximates \(p_{d}:[0,k]^{d}\longrightarrow\mathbb{R}\), defined by \(p_{d}(\textbf{x})=\frac{1}{k^{4}}\prod_{i=1}^{d}x_{i}\), with \(n=\text{poly}(d)\)._

The full proof can be found in Appendix A.1. This proof is constructive and is built upon the following observation: a polynomial \(q_{r}\) of degree \(r\), which depends solely on \(\varepsilon^{-1}\), exists that \(\varepsilon\)-approximates the univariate function \(x\mapsto e^{x}\). Thus, we have:

\[p_{d}(\textbf{x})=\exp\bigg{(}\sum_{i=1}^{d}\ln x_{i}\bigg{)}\approx q_{r} \bigg{(}\sum_{i=1}^{d}\ln x_{i}\bigg{)} \tag{3}\]

which reduces the problem to approximating polynomials of degree at most \(r\) in the \(d\) variables \((\ln x_{i})_{i=1}^{d}\). Observe that there are only \(\binom{d+r}{r}\leq(d+1)^{r}\) elements in the right-hand side of equation (3). This observation enables us to "flatten" the network in Theorem 4 into a one-hidden-layer network. As suggested by Theorem 3, the normalization factor in equation (2) is critical for the proof. Similar flattening results are shown in Safran et al. (2019) Theorem 1 (for Lipschitz radial functions) and in the more general Venturi et al. (2021) Theorem 11 (using Fourier networks). The crux of the proof is demonstrating that the product function meets the conditions of the latter result, with the remaining details presented in a simplified form for completeness.

**Proof Sketch.** Essentially, we construct a two-layer network akin to Theorem 4 with the \(\exp\) activation function and then employ the framework previously described to demonstrate that flattening to a shallow network is feasible with a polynomial cost in complexity.

The high-level strategy for this proof proceeds in several key stages. Initially, a two-hidden-layer network is constructed with the \(\exp:x\mapsto e^{x}\) activation function, such that \(\hat{f}(\textbf{x})=\exp\bigg{(}\sum_{i=1}^{n}\nu_{i}\exp(\textbf{w}_{i} \textbf{x})\bigg{)}\) approximates \(p_{d}\). Additionally, it is demonstrated that it is feasible to control the value of the coefficients within the network.

Following this, the proof establishes that the non-linearity of the second hidden layer can be approximated by a polynomial with a linear cost in \(\varepsilon^{-1}\). For a specific univariate polynomial \(q\), whose degree depends solely on \(\varepsilon\), \(\hat{f}\) is substituted by

\[q\bigg{(}\sum_{i=1}^{n}\nu_{i}\exp(\textbf{w}_{i}\textbf{x})\bigg{)} \tag{4}\]
It is important to note that the normalization factor in (2) is essential for this stage of the proof. We then leverages properties of the exponential function, specifically the fact that \(\exp(\mathbf{w}\mathbf{x})^{m}=\exp((m\mathbf{w})\mathbf{x})\), to demonstrate that (4) is a shallow \(\exp\) network. An analogous result for shallow Fourier neural networks is presented in Venturi et al. (2021) Lemma 33. The proof is completed by demonstrating that the \(\exp\) activation function in the shallow network can be replaced with the ReLU activation function.

## 6 Conclusion

We have established results describing the expressive power of \(\mathcal{O}(1)\)-ReLU-networks in the context of approximating the class of homogeneous multivariate polynomials.

**Deep vs shallow**. Our investigation provides further evidence that deep ReLU networks demonstrate superior efficiency in expressing homogeneous polynomials. The number of computational units necessary for expressing the product function diminishes significantly with increased depth, as evidenced by the lower bound in Theorem 3. With \(L=\log d\) layers, a deep network can efficiently express this function.

**The curse of dimensionality.** Our findings suggest that the product function can be efficiently expressed using a neural network if the network is sufficiently deep to exploit the computational structure of the function (Poggio et al. (2017)), or if it operates on a domain in which its Lipschitz constant does not grow with the dimension. This observation aligns with the surprising recent result in Safran et al. (2019). In their respective works, Daniely (2017) and Eldan and Shamir (2016) demonstrated that functions of the form \(x\mapsto\varphi(||x||)\) can be approximated by depth-two networks, leveraging the computational structure. However, unless \(\varphi\) is \(\mathcal{O}(1)\)-Lipschitz (Safran et al. (2019)), it cannot be expressed efficiently using a one-hidden-layer network.