Optimal Approximation Complexity of High-Dimensional Functions with
  Neural Networks
We investigate properties of neural networks that use both ReLU and $x^2$ as
activation functions and build upon previous results to show that both analytic
functions and functions in Sobolev spaces can be approximated by such networks
of constant depth to arbitrary accuracy, demonstrating optimal order
approximation rates across all nonlinear approximators, including standard ReLU
networks. We then show how to leverage low local dimensionality in some
contexts to overcome the curse of dimensionality, obtaining approximation rates
that are optimal for unknown lower-dimensional subspaces.
Vincent P. H. Goverse, Jad Hamdan, Jared Tanner
# Optimal approximation complexity of high-dimensional functions with neural networks

###### Abstract.

We investigate properties of neural networks that use both ReLU and \(x^{2}\) as activation functions and build upon previous results to show that both analytic functions and functions in Sobolev spaces can be approximated by such networks of constant depth to arbitrary accuracy, demonstrating optimal order approximation rates across all nonlinear approximators, including standard ReLU networks. We then show how to leverage low local dimensionality in some contexts to overcome the curse of dimensionality, obtaining approximation rates that are optimal for unknown lower-dimensional subspaces.

Key words and phrases:Machine Learning, Universal Approximation, bi-activation, Neural Networks 2020 Mathematics Subject Classification: 41A10

## 1. Introduction

The number of parameters needed to approximate smooth high-dimensional functions, \(W^{n,\infty}([0,1]^{d})\), within a prescribed \(\epsilon\) accuracy in the \(\ell_{\infty}\) norm was lower bounded by [6] to have a dependence on \(\epsilon\) that is proportional to \(\epsilon^{-d/n}\). [16] has subsequently shown that a simple feed-forward neural network with \(\text{ReLU}(x):=\max\{0,x\}\) nonlinear activation is nearly optimal in terms of the number of parameters needed, requiring only \(c(n,d)=\epsilon^{-d/n}\log(1/\epsilon)\) parameters1, see [16][Theorem 1]. Subsequently, [4] reduced the number of parameters needed by a feedforward neural network to achieve \(\epsilon\) accuracy to being proportional to \(c(n,d)=\epsilon^{-d/n}\log(\log(1/\epsilon))\) by using trainable rational function as nonlinear activations, see [4][Theorem 4].

Footnote 1: The function \(c(n,d)\) depends on the smoothness, \(n\), and the dimension of \(f(x)\), but not on the desired accuracy \(\epsilon\).

Here we further adapt the proof by Yarotsky to achieve the optimal dependence of \(\epsilon^{-d/n}\) proven by [6], using a feedforward network that makes use of _two_ nonlinear activations (henceforth referred to as _bi-activation_ networks). Specifically, we allow some layers to use the ReLU nonlinear activation to localize \(f(x)\) through a partition of unity, and the quadratic activation \(x^{2}\) to allow for efficient computation of localized high degree polynomial approximations.

Specifically, following the notation of [6] and [16], we consider nonlinear approximation methods \(M_{p}(a)\) that have a continuous dependence2 on the \(p\) parameters \(a\in\mathbb{R}^{p}\) and which approximate high dimensional functions \(f(\cdot)\) within the unit ball of the Sobolev space \(W^{n,\infty}([0,1]^{d})\),

Footnote 2: The continuous dependence of \(M_{n}(a)\) on \(a\) is introduced in [6] to avoid space filling curves and can be viewed as ensuring the parameters \(a\) can be learned from a sufficiently near estimate; for details see [6].

\[||f||_{W^{n,\infty}([0,1]^{d})}=\max\;_{\mathbf{n}\in|\mathbf{n}|\leq n}\text{ esssup}_{\mathbf{x}\in[0,1]^{d}}|D^{\mathbf{n}}f(\mathbf{x})| \tag{1.1}\]
## 1. Introduction

In this paper we consider the following problem:

\[\min_{a\in\mathbb{R}^{d}}\max_{x\in[0,1]^{d}}|f(x)-M_{\mathcal{C}_{F}, bi-\sigma}(a)(x)|\leq\epsilon \tag{1}\]

where \(\mathcal{C}_{F}\) is a fixed fixed constant.

The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant. The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant. The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant. The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant.

The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant. The problem of finding a fixed constant \(d\) is NP-hard if and only if \(\mathcal{C}_{F}\) is a fixed constant.
**Theorem 1.4** (Optimal approximation order bi-activation networks: Analytic functions).: _Let \(f(x)\) be an analytic function on \([0,1]^{d}\), characterised \([1]\) by_

\[\sup_{x\in[0,1]^{d}}\left|\frac{\partial^{n}f}{\partial x^{n}}(x)\right|\leq C _{f}^{|\mathbf{n}|+1}\mathbf{n}!\quad\text{for}\;\;\text{all}\;n \tag{1.2}\]

_where \(C_{f}\) depends on the particular choice of \(f(x)\). Then for any \(d\), and \(\epsilon\in(0,1)\), there exists \(M_{\mathcal{C}_{A},bi-\sigma}(a)\) formed as a feed-forward network with \(\mathcal{C}_{A}=C_{4}(d,C_{f})\left((2\epsilon)^{\log^{-\frac{1}{2}}\left( \frac{2^{d}}{\epsilon}\right)}\log^{\frac{d}{2}}\left(\frac{1}{\epsilon} \right)\right)\) elements \(a\in\mathbb{R}^{\mathcal{C}_{A}}\) for which_

\[\min_{a\in\mathbb{R}^{\mathcal{C}_{A}}}\max_{x\in[0,1]^{d}}|f(x)-M_{\mathcal{ C}_{A},bi-\sigma}(a)(x)|\leq\epsilon\]

_where \(C_{4}(d,C_{f})\) does not depend on \(\epsilon\)._

Theorem 1.4 differs from Theorem 1.3 primarily in the lack of dependence on smoothness \(n\) as the number of parameters \(\mathcal{C}_{\mathcal{A}}\) needed in the network has been minimized over all admissible \(n\). The consequence of choosing the optimal smoothness \(n\) is that the \(\epsilon\) and \(d\) dependence of the number of parameters \(\mathcal{C}_{\mathcal{A}}\) decreases from \((\epsilon^{-1/n})^{d}\) to predominantly \(\log(1/\epsilon)^{d/2}\).

Next, for \(d_{\text{eff}}<d\) we define the canonical subspace of \([0,1]^{d}\) of dimension \(d_{\text{eff}}\); that is

\[x\in\chi_{d_{\text{eff}},e}^{d}:=\{x\in[0,1]^{d}:\;\text{with if}\;i\notin e,x _{i}=0\}.\]

Where \(e\) is a subset of \(\{1,\ldots,d\}\), with \(d_{\text{eff}}\) elements. \(I_{d_{\text{eff}}}^{d}\) is the collections of all \(e\). Then if \(f(x)\) is nonzero on only one known subspace \(\chi_{d_{\text{eff}},e}^{d}\) Lemma 2.2 holds. In the case that \(f(x)\) is nonzero on the union of all \(\binom{d}{d_{\text{eff}}}\) such subspaces

\[\bar{\chi}_{d_{\text{eff}}}^{d}:=\bigcup_{e\in I}\chi_{d_{\text{eff}},e}^{d},\]

the number of parameters \(\mathcal{C}_{M}\) needed to compute an \(\epsilon\) approximation of \(f(x)\) over one or all canonical subspaces is given by \(\mathcal{C}_{M}=C_{5}(d,d_{\text{eff}},n)\epsilon^{-d_{\text{eff}}/n})\) (see Lemma 2.2 and Theorem 1.5).

**Theorem 1.5** (Optimal approximation order bi-activation networks: low-dimensional subspaces).: _For function \(f(x)\) with \(||f||_{W^{n,\infty}([0,1]^{d})}\leq 1\) where \(x\) is restricted to \(\bar{\chi}_{d_{\text{eff}}}^{d}\), there exists \(M_{\mathcal{C}_{M},bi-\sigma}(a)\) formed as a feed-forward network with \(\mathcal{C}_{M}=C_{5}(d,n)\epsilon^{-d_{\text{eff}}/n}\) elements \(a\in\mathbb{R}^{\mathcal{C}_{M}}\) for which the error restricted on \(\chi_{d_{\text{eff}}}^{d}\) is_

\[\min_{a\in\mathbb{R}^{\mathcal{C}_{M}}}\max_{x\in\bar{\chi}_{d_{\text{eff}}}^{ d}}|f(x)-M_{\mathcal{C}_{M},bi-\sigma}(a)(x)|\leq\epsilon\]

_where \(C_{5}(d,n)\) may depend on \(d\) and \(n\), but not on \(\epsilon\)._

This restricted subspace model is motivated by natural image inputs with prescribed compression on a known orthogonal basis, such as JPEG compression. This union of subspace model \(\bar{\chi}_{d_{\text{eff}}}^{d}\) is also widely used in the theory of compressed sensing, see [7] and references therein, and has also been used to increase robustness against adversarial attacks on image classification by [9].
## 2. Approximation power of bi-activation networks

The proof of Theorem 1.3 being adapted from that 1.2 in [16], an understanding of the former is essential in order to explain the latter.

As mentioned previously, [16] first partitions the input \(x\in[0,1]^{d}\) into exponentially many localized portions using a partition of unity \(\{\phi_{\mathbf{m}}\}\), where each \(\phi_{\mathbf{m}}\) is piecewise linear and expressible by a ReLU network with a constant number of parameters (see Proposition 1 in [16]). The aim is then to approximate the function \(f\) by Taylor polynomials locally, giving the following representation for an approximation of \(f\).

**Lemma 2.1** ([16]).: _Let \(\epsilon>0\) be arbitrary and \(f\in W^{n,\infty}([0,1]^{d})\). Then there exists a function \(\tilde{f}\) expressible as_

\[\tilde{f}(x)=\sum_{\mathbf{m}\in\{0,\ldots,N\}^{d}}\sum_{\mathbf{m}:|\mathbf{ n}|<n}a_{\mathbf{m},\mathbf{n}}\phi_{\mathbf{m}}(x)\left(x-\frac{\mathbf{m}}{N} \right)^{\mathbf{n}},\]

_where \(a_{m,n}\in\mathbb{R}\), \(|a_{m,n}|\leq 1\), \(\{\phi_{\mathbf{m}}\}_{\mathbf{m}\in\{0,1,\ldots,N\}^{d}}\) is a partition of unity such that each \(\phi_{\mathbf{m}}\) is given by a product of \(d\) piecewise linear univariate factors. Furthermore, \(\tilde{f}\) is such that_

\[|f(x)-\tilde{f}(x)|\leq\frac{2^{d}d^{n}}{n!}\left(\frac{1}{N}\right)^{n}\max_ {\mathbf{n}:|\mathbf{n}|=n}\text{ess sup}_{x\in[0,1]^{d}}|D^{\mathbf{n}}f(x)|. \tag{2.1}\]

_The proof of this lemma is included in the appendix for completeness._

Showing that ReLU networks can approximate monomials (and, in turn, polynomials) would then complete the proof. Indeed, in Section 3.1 of [16], the author does so by first showing that \(f(x)=x^{2}\) can be approximated by a ReLU network of complexity \(O(\ln(1/\epsilon))\). Using the following identity to recover multiplication from squaring:

\[xy=\frac{1}{2}\big{(}(x+y)^{2}-x^{2}-y^{2}\big{)} \tag{2.2}\]

the author then shows how a ReLU network of complexity \(O(\ln(1/\epsilon))\) can in fact approximate terms of the form \(\phi_{\mathbf{m}}(x)\left(x-\frac{\mathbf{m}}{N}\right)^{\mathbf{n}}\).

Lastly, note that in lemma 2.1, \(\tilde{f}\) is a linear combination of at most \(d^{n}(N+1)^{d}\) such terms. \(N\) is a smoothness parameter that can be chosen so that the upper bound in (2.1) becomes \(|f(x)-\tilde{f}(x)|<\epsilon\). In Yarotsky's case, this corresponds to choosing

\[N=N(\epsilon,d,n)=\left\lceil\left(\frac{n!}{2^{d}d^{n}}\epsilon\right)^{-1/n }\right\rceil, \tag{2.3}\]

which also yields

\[d^{n}(N+1)^{d}=d^{n}\left(\frac{n!}{2^{d}d^{n}}\epsilon\right)^{-d/n}=O( \epsilon^{-d/n}),\]

and the final ReLU network used approximate \(f\) therefore consists of \(\mathcal{C}_{Y}=O(\epsilon^{-d/n}\ln(1/\epsilon))\) parameters due to the \(\log(1/\epsilon)\) depth needed to approximate \(x^{2}\) within \(\epsilon\) using a ReLU network.

### Proof of Theorem 1.3, Optimal approximation order bi-activation networks

Proof of Theorem 1.3.: Let \(\tilde{f}\) be the approximation to \(f\) given by Lemma 2.1. Since \(f\) is in the unit-ball in \(W^{n,\infty}\), \(\max_{\mathbf{n}:|\mathbf{n}|=n}\text{ess sup}_{x\in[0,1]^{d}}|D^{\mathbf{n}} f(x)|\leq 1\). Choosing the same \(N\) as in 2.3, we find that \(||f-\tilde{f}||_{\infty}\leq\epsilon\).
In contrast to ReLU networks, we claim that bi-activation networks can represent terms of the form \(\phi_{\mathbf{m}}(x)(x-\mathbf{m}/N)^{\mathbf{n}}\)_exactly_ using a constant number of trainable parameters. Indeed, each of these terms is itself a product of at most \(d+n-1\) piecewise linear univariate factors: a product of \(d\) functions defining each \(\phi_{\mathbf{m}}\) and at most \(n-1\) functions \(x_{k}-m_{k}/N\). These products can be implemented by a bi-activation network with a complexity of the order of \((n+d)\) and depth of the order of \(\log_{2}(n+d)\) (in both cases, \(O(1)\) with respect to \(\epsilon\)), by repeatedly pairing up the terms and multiplying them in tournament fashion (see figure 1). The multiplication of two terms can be achieved by a bi-activation network of constant size using (2.2)3.

Footnote 3: More specifically, we can use a network with activation function \(x^{2}\) which has one hidden layer. The inputs \(x\) and \(y\) connect fully to the hidden layer with three nodes, and weights \([0,1],[1,0]\) and \([1,1]\). The three nodes are connected to the output with weight \([-1/2,-1/2,1/2]\).

Therefore, \(\tilde{f}\) can be written by a bi-activation network \(M_{\mathcal{C}_{F},bi-\sigma}(a)\) with \(\mathcal{C}_{F}=O(d^{n}(N+1)^{d})\) parameters as follows. The network uses parallel subnetworks that each compute a term in the series defining \(\tilde{f}\), and computes the final output by summing the outputs of these subnetworks, weighted with the appropriate \(a_{\mathbf{m},\mathbf{n}}\). Since there are not more than \(d^{n}(N+1)^{d}\) subnetworks, \(\mathcal{C}_{F}=C_{3}(d,n)d^{n}(N+1)^{d}\) weights and computation units, for some constant \(C_{3}(d,n)\). For our choice of \(N\) in (2.3) to achieve an \(\epsilon\) accurate approximation, \(\mathcal{C}_{F}=O(\epsilon^{-d/n})\). 

### Proof of Theorem 1.4, Optimal approximation order bi-activation networks: Analytic functions

Proof of Theorem 1.4.: Once again, let \(\tilde{f}\) be the approximation to \(f\) given by Lemma 2.1, noting that \(f\in W^{n,\infty}([0,1]^{d})\) for all \(n\) as it is analytic. Then applying the bound on \(|f(x)-\tilde{f}(x)|\) given by the same Lemma and the bound on smoothness for analytic functions (1.2), we find that

\[|f(x)-\tilde{f}(x)| \leq\frac{2^{d}d^{n}}{n!}\left(\frac{1}{N}\right)^{n}\max_{ \mathbf{n}:|\mathbf{n}|=n}\text{ess sup}_{x\in[0,1]^{d}}|D^{\mathbf{n}}f(x)|\] \[\leq\frac{2^{d}d^{n}}{n!}\left(\frac{1}{N}\right)^{n}C_{f}^{n+1}n!\] \[\leq 2^{d}d^{n}\left(\frac{C_{f}}{N}\right)^{n+1}\,,\]

Figure 1. Multiplication of \(k\) elements (depicted in black) using \(O(k)\) subnetworks (depicted in red) each of constant size (independent of \(d\) and \(n\)), giving a network of depth \(O(\ln_{2}(k))\). Here, \(k=8\).
where \(C_{f}\) is a constant depending on \(f\).

Notice that in this case the result holds for all \(n\). This means that, when picking \(N\), we can optimize over \(n\) to minimize the number of trainable parameters needed by our network. To begin with, choosing

\[N_{1}=N(C_{f},\epsilon,d,n)=\frac{1}{C}\left[\left(\frac{\epsilon}{2^{d}d^{n}} \right)^{-1/(n+1)}\right] \tag{2.4}\]

we get that \(||f-\tilde{f}||_{\infty}\leq\epsilon\).

Arguing in the exact same manner as in the proof of Theorem 1.3, we know that \(\tilde{f}\) can be written as a bi-activation neural network \(M_{\mathcal{C}_{A},bi-\sigma}(a)\). The total number of parameters \(\mathcal{C}_{A}\) then needed by the network to represent \(\tilde{f}\) is equal to

\[\mathcal{C}_{A}=C_{4}(C_{f},n,d)d^{n}(N+1)^{d} \tag{2.5}\]

for some constant \(C_{4}=C_{4}(C_{f},n,d)\) that does not depend on \(\epsilon\). Substituting the choice of \(N\) in (2.4) in (2.5) and minimizing over \(n\), we find that \(\mathcal{C}_{\mathcal{A}}\) is minimal for

\[n_{\min}=\sqrt{\frac{d\left(d\log(2)+\log\left(\frac{1}{\epsilon}\right) \right)}{\log(d)}}. \tag{2.6}\]

Substituting (2.6) and (2.4) into (2.5), gives us

\[\mathcal{C}_{A}=C_{4}\cdot 2^{\frac{d^{3/2}\sqrt{\log(d)}}{\sqrt{d\log(2)+ \log\left(\frac{1}{\epsilon}\right)}}}\epsilon^{\frac{\sqrt{d}\sqrt{\log(d)}}{ \sqrt{d\log(2)+\log\left(\frac{1}{\epsilon}\right)}}}\log^{\frac{d}{2}}\left( \frac{1}{\epsilon}\right),\]

which grows as \(\epsilon\to 0\) in the order of

\[(2\epsilon)^{\log^{-\frac{1}{2}\left(\frac{2^{d}}{\epsilon}\right)}}\log^{ \frac{d}{2}}\left(\frac{1}{\epsilon}\right),\]

concluding the proof.

### Proof of Theorem 1.5, Optimal approximation order bi-activation networks: low-dimensional subspaces

For clarity, first consider the simplest case of \(x\in\chi_{d_{\mathrm{eff}},e}^{d}\), for a known \(e\in I\). Without loss of generality this can be the first \(d_{\mathrm{eff}}\) dimensions of \(\mathbb{R}^{d}\) being nonzero, that is \(f\circ A(x):=f(Ax)\) for \(A\in\mathbb{R}^{d\times d_{\mathrm{eff}}}\) given by

\[A=\begin{pmatrix}1&0&\dots&0&0\\ 0&1&&0&0\\ \vdots&&\ddots&&\vdots\\ 0&0&&1&0\\ 0&0&&0&1\\ 0&0&\dots&0&0\end{pmatrix}. \tag{2.7}\]

In this case we have \(f|_{\chi_{d_{\mathrm{eff}},e}^{d}}=f\circ A\). When we consider that the function we try to approximate is of the form \(f\circ A\), we get the following lemma.

**Lemma 2.2** (Optimal approximation order bi-activation networks: low-dimensional single subspace).: _For function \(f(x)\) with \(||f||_{W^{n,\infty}([0,1]^{d})}\leq 1\) where \(x\) is restricted to a single
canonical subspace \(\chi_{d_{\text{eff}},e}^{d}\), there exists \(M_{\mathcal{C}_{S},bi-\sigma}(a)\) formed as a feed-forward network with \(\mathcal{C}_{S}=C_{6}(d,n)\epsilon^{-d_{\text{eff}}/n}\) elements \(a\in\mathbb{R}^{\mathcal{C}_{S}}\) for which_

\[\min_{a\in\mathbb{R}^{\mathcal{C}_{S}}}\max_{x\in\chi_{d_{\text{eff}},e}^{d}}| f(x)-M_{\mathcal{C}_{S},bi-\sigma}(a)(x)|\leq\epsilon\]

_where \(C_{6}(d,n)\) may depend on \(d\) and \(n\), but not on \(\epsilon\)._

We prove Lemma 2.2, by showing that \(\|f\circ A\|_{W^{n,\infty}[0,1]^{d_{\text{eff}}}}\leq 1\) and then applying Theorem 1.3.

Proof.: For a fixed \(d,n\in\mathbb{N}\), \(d_{\text{eff}}\in\mathbb{N}\) such that \(d_{\text{eff}}<d\) and \(\epsilon\in(0,1)\). We consider without loss of generality a \(f\) and \(A\) as prescribed, then by upper bounding \(\|f\circ A\|_{W^{n,\infty}([0,1]^{d_{\text{eff}}})}\) by \(1\), we can apply Theorem 1.3. We have for a \(\mathbf{n}\), with \(|\mathbf{n}|=n\) that

\[\begin{split}&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}}|D^{\mathbf{n}}(f\circ A)(x)|\\ =&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}}| \partial_{x_{1}}^{n_{1}}\partial_{x_{2}}^{n_{2}}\ldots\partial_{x_{d_{\text{ eff}}}}^{n_{d_{\text{eff}}}}(f\circ A)(x)|\\ =&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}} \left|\partial_{x_{1}}^{n_{1}}\partial_{x_{2}}^{n_{2}}\ldots\partial_{x_{d_{ \text{eff}}}}^{n_{d_{\text{eff}}}-1}\sum_{i=1}^{d}\partial_{x_{i}}(f)(Ax)\cdot A _{id_{\text{eff}}}\right|\\ =&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}}| \partial_{x_{1}}^{n_{1}}\partial_{x_{2}}^{n_{2}}\ldots\partial_{x_{d_{\text{ eff}}}}^{n_{d_{\text{eff}}}-1}\partial_{x_{d_{\text{eff}}}}(f)(Ax)\cdot A _{d_{\text{eff}}d_{\text{eff}}}\Big{|}\\ =&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}} \left|\partial_{x_{1}}^{n_{1}}\partial_{x_{2}}^{n_{2}}\ldots\partial_{x_{d_{ \text{eff}}}}^{n_{d_{\text{eff}}}}(f)(Ax)\right|\\ =&\text{esssup }_{x\in[0,1]^{d_{\text{eff}}}}|D^{ \mathbf{n}}(f)(Ax)|\\ \leq&\text{esssup }_{x\in[0,1]^{d}}|D^{\mathbf{n}}(f)(x)|\leq 1. \end{split} \tag{2.8}\]

Here in (2.8) we use the argument above \(|\mathbf{n}|\) times. Taking the maximum over \(\mathbf{n}\) gives us that

\[\|f\circ A\|_{W^{n,\infty}([0,1]^{d_{\text{eff}}})}\leq 1.\]

To finish the proof we apply Theorem 1.3. 

The reason we introduce the previous lemma is that for all canonical subspaces of dimension \(d_{\text{eff}}\), we can assume without loss of generality that there exists a matrix \(A\) of the form of (2.7).

Proof of Theorem 1.5.: For any \(d,n,d_{\text{eff}}\in\mathbb{N}\) such that \(d_{\text{eff}}<d\) and \(\epsilon\in(0,1)\), we define \(\hat{f}:[0,1]^{d}\rightarrow\mathbb{R}\), as \(\hat{f}|_{\tilde{\chi}_{d_{\text{eff}},e}^{d}}=\tilde{f}\), for all \(e\in I\) where \(\tilde{f}\) is as in Lemma 2.2, and zero elsewhere. Then for \(\hat{f}\) we have:

\[\sup_{x\in\tilde{\chi}_{d_{\text{eff}}}^{d}}|\hat{f}(x)-f(x)|\leq \sum_{e\in I}\sup_{x\in\chi_{d_{\text{eff}},e}^{d}}|\hat{f}(x)-f (x)|\leq\frac{2^{d_{\text{eff}}}d_{\text{eff}}^{n}}{n!}\left(\frac{1}{N} \right)^{n}\binom{d}{d_{\text{eff}}}. \tag{2.9}\]

Setting

\[N=N(\epsilon,d,d_{\text{eff}},n)=\left[\left(\frac{n!\binom{d}{d_{\text{eff}}}} {2^{d_{\text{eff}}}d_{\text{eff}}{n}^{n}}\epsilon\right)^{-1/n}\right]\]

and plugging \(N\) in (2.9), we get \(\sup_{x\in\chi_{d_{\text{eff}}}^{d}}|\hat{f}(x)-f(x)|\leq\epsilon\). Furthermore, by Lemma 2.2\(\tilde{f}\) can be implemented as a feed-forward network \(M_{\mathcal{C}_{S},bi-\sigma}(a)(x)\). Then \(\hat{f}\) can be formed as the product
of these networks, which results in a total feed-forward network \(M_{\mathcal{C}_{M},bi-\sigma}(a)(x)\), where

\[\mathcal{C}_{M}=\binom{d}{d_{\text{eff}}}d_{\text{eff}}{}^{n}(N+1)^{d_{\text{ eff}}}=C_{5}(d,d_{\text{eff}},n)\epsilon^{-d_{\text{eff}}/n},\]

which finishes our proof. 

**Remark 2.3**.: Although the networks in the case of Lemma 2.2 and Theorem 1.5 have the same \(\epsilon\) functional dependence in their number of parameters, the total size of the network \(\mathcal{C}_{\mathcal{S}}\) and \(\mathcal{C}_{\mathcal{M}}\) will be different, as they also depend in a different way on \(d,d_{\text{eff}}\) and \(n\).

## 3. Conclusions

We have shown that bi-activation networks, which use both the ReLU and \(x^{2}\) as activation functions, have greater approximation power than ReLU networks. By repurposing a proof of [16] for ReLU networks, we have derived upper bounds for the number of parameters needed by bi-activation networks to approximate functions in the unit ball of the Sobolev space \(W^{n,\infty}([0,1]^{d})\) achieving the optimal order \(O(\epsilon^{-d/n})\) number of parameters as lower bounded by [6]. We also extended our result to analytic functions on \([0,1]^{d}\) for yet superior \(\epsilon\) dependence and to low-dimensional subspaces to overcome the curse of dimensionality.

Natural extensions of these results are 1) to determine if a feedforward, or another network, with a single nonlinear activation can achieve the optimal order \(O(\epsilon^{-d/n})\) number of parameters, and 2) to consider further low-complexity models of \(f(x)\) beyond the union of subspaces, see for instance the nested structure considered in [14].

## Acknowledgments

VG and JH would like to thank the EPSRC Centre for Doctoral Training in Mathematics of Random Systems: Analysis, Modelling and Simulation (EP/S023925/1) for its support. JT is supported by the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA) and thanks UCLA Department of Mathematics for kindly hosting him during the completion of this manuscript.
