Deep neural network approximation of composite functions without the
  curse of dimensionality
In this article we identify a general class of high-dimensional continuous
functions that can be approximated by deep neural networks (DNNs) with the
rectified linear unit (ReLU) activation without the curse of dimensionality. In
other words, the number of DNN parameters grows at most polynomially in the
input dimension and the approximation error. The functions in our class can be
expressed as a potentially unbounded number of compositions of special
functions which include products, maxima, and certain parallelized Lipschitz
continuous functions.
Adrian Riekert
# Deep neural network approximation of composite functions without the curse of dimensionality

###### Abstract.

In this article we identify a general class of high-dimensional continuous functions that can be approximated by deep neural networks (DNNs) with the rectified linear unit (ReLU) activation without the curse of dimensionality. In other words, the number of DNN parameters grows at most polynomially in the input dimension and the approximation error. The functions in our class can be expressed as a potentially unbounded number of compositions of special functions which include products, maxima, and certain parallelized Lipschitz continuous functions.

Key words and phrases:Approximation error, curse of dimensionality, artificial neural networks

## 1. Introduction

Many practically relevant numerical approximation algorithms suffer from the curse of dimensionality (cf., e.g., Bellman [2] and Novak & Ritter [27]). Roughly speaking, this means that the number of parameters needed to approximate certain functions grows exponentially in the input dimension, which is often problematic in high dimensions. In recent years deep neural networks (DNNs) have been successfully employed in numerous high-dimensional applications, where the unknown function to be approximated can depend on thousands or even millions of real parameters. It thus seems that DNNs are able to overcome the curse of dimensionality in many relevant cases. Nevertheless, the reasons for these promising practical results are still not fully understood.

In this article we aim to enhance the understanding of the approximation capabilities of DNNs by identifying a suitably large class of continuous functions that can provably be approximated by DNNs without the curse of dimensionality. That is, the number of DNN parameters is allowed to grow at most polynomially with respect to the input dimension and the prescribed approximation accuracy. The functions in this class can be expressed as compositions of particular functions which include products, maxima, and parallelized Lipschitz continuous functions; and the number of functions in the composition itself is allowed to grow polynomially in the input dimension, which leads to interesting new examples of approximable functions.

### Literature overview

The fact that neural networks with a suitable activation function and sufficiently many parameters can approximate any continuous function up to an arbitrarily small error is known in the literature as the universal approximation theorem. Qualitative results of this type were first established, e.g., in [5, 8, 14, 15, 19]. We also refer to Pinkus [29] for further references regarding such universal approximation results.

Quantitative upper bounds on the number of DNN parameters needed to approximate continuous functions can be found, e.g., in [9, 21, 29, 33, 35]. These estimates suffer from the curse of dimensionality, since one needs \(\Omega(\varepsilon^{-cd})\) DNN parameters to approximate
## 1. Introduction

### Background

The study of the _generalized
This is the measure we use to describe the complexity of the neural network \(\Phi\).

For every \(p\in[1,\infty]\), every \(d\in\mathbb{N}\) and every \(x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}\) the \(\ell_{p}\)-norm of \(x\) is defined by

\[\|x\|_{p}=\begin{cases}\left(|x_{1}|^{p}+\cdots+|x_{d}|^{p}\right)^{1/p}&:p< \infty\\ \max\{|x_{1}|,\ldots,|x_{d}|\}&:p=\infty.\end{cases}\]

For every \(n\in\mathbb{N}_{0}=\mathbb{N}\cup\{0\}=\{0,1,2,\ldots\}\) we write \([n]=\mathbb{N}\cap(0,n]=\{1,2,\ldots,n\}\).

We now introduce the special function classes we consider throughout the remainder of this article. Firstly, we consider for \(d\in\mathbb{N}\) the multidimensional maximum and product functions \(m_{d},p_{d}\colon\mathbb{R}^{d}\to\mathbb{R}\) and \(\mathfrak{m}_{d},\mathfrak{p}_{d}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}\) which satisfy for all \(x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}\) that

\[\begin{split} m_{d}(x)&=\max\{x_{1},\ldots,x_{d}\}, \\ p_{d}(x)&=\prod_{i=1}^{d}x_{i},\\ \mathfrak{m}_{d}(x)&=(m_{1}(x_{1}),m_{2}(x_{1},x_{2 }),\ldots,m_{d}(x_{1},\ldots,x_{d})),\\ \mathfrak{p}_{d}(x)&=(p_{1}(x_{1}),p_{2}(x_{1},x_{2 }),\ldots,p_{d}(x_{1},\ldots,x_{d})).\end{split} \tag{1.2}\]

Furthermore, for every \(n\in\mathbb{N}\), \(d_{1},\ldots,d_{n}\), \(e_{1},\ldots,e_{n}\in\mathbb{N}\), subsets \(A_{i}\subseteq\mathbb{R}^{d_{i}}\), and arbitrary functions \(f_{i}\colon A_{i}\to\mathbb{R}^{e_{i}}\), \(i\in[n]\), we denote by \((f_{1}\square f_{2}\square\cdots\square f_{n})\colon A_{1}\times A_{2}\times \cdots\times A_{n}\to\mathbb{R}^{\sum_{i=1}^{n}e_{i}}\) the _parallelization_ of \(f_{1},\ldots,f_{n}\), i.e., the function which satisfies for all \(x_{1}\in A_{1},\ldots,x_{n}\in A_{n}\) that

\[(f_{1}\square f_{2}\square\cdots\square f_{n})(x_{1},x_{2},\ldots,x_{n})=(f_{ 1}(x_{1}),f_{2}(x_{2}),\ldots,f_{n}(x_{n})). \tag{1.3}\]

Now let \(Q\) be a (\(d\)-dimensional) _hypercube_, by which we in the following mean a set of the form \(Q=[a,b]^{d}\subseteq\mathbb{R}^{d}\). Here \(d\in\mathbb{N}\) is an arbitrary natural number which describes the input dimension and \(a\in\mathbb{R}\), \(b\in(a,\infty)\) are real numbers which describe the input domain. For every \(k\in\mathbb{N}\), \(p\in[1,\infty]\), \(L\in[0,\infty)\) we denote by \(\mathscr{A}_{k,p}(Q,L)\subseteq\bigcup_{n\in\mathbb{N}}C(Q,\mathbb{R}^{n})\) the set of all continuous functions \(f\) on \(Q\) for which there exist \(n\in\mathbb{N}\), \(d_{1},\ldots,d_{n}\in\mathbb{N}\), and functions \(f_{i}\colon[a,b]^{d_{i}}\to\mathbb{R}\), \(i\in[n]\), such that

\[\begin{split}\sum\limits_{i=1}^{n}d_{i}=d,&\max_{i \in[n]}d_{i}\leq k,\qquad\forall\,i\in[n],\,x,y\in[a,b]^{d_{i}}\colon|f_{i}(x) -f_{i}(y)|\leq L\|x-y\|_{p},\\ \text{and}&\quad f=f_{1}\square f_{2}\square\cdots \square f_{n}.\end{split}\]

That is, \(f\) is the parallelization of functions defined on domains of dimension at most \(k\) which are Lipschitz with respect to the \(p\)-norm with Lipschitz constant \(L\).

We also denote by \(\mathbf{M}(Q)\subseteq\bigcup_{n\in\mathbb{N}}C(Q,\mathbb{R}^{n})\) the set of all continuous functions \(f\) on \(Q\) for which there exist \(n\in\mathbb{N}\) and \(d_{1},\ldots,d_{n}\in\mathbb{N}\) such that \(\sum_{i=1}^{n}d_{i}=d\) and

\[f=(m_{d_{1}}|_{[a,b]^{d_{1}}})\square(m_{d_{2}}|_{[a,b]^{d_{2}}})\square\cdots \square(m_{d_{n}}|_{[a,b]^{d_{n}}}),\]

i.e., the parallelizations of the maximum functions \(m_{d_{i}}\).

Finally, we denote by \(\mathbf{P}(Q)\subseteq\bigcup_{n\in\mathbb{N}}C(Q,\mathbb{R}^{n})\) the set of all continuous functions \(f\) on \(Q\) for which there exist \(n\in\mathbb{N}\) and \(d_{1},\ldots,d_{n}\in\mathbb{N}\) such that \(\sum_{i=1}^{n}d_{i}=d\) and

\[f=(p_{d_{1}}|_{[a,b]^{d_{1}}})\square(p_{d_{2}}|_{[a,b]^{d_{2}}})\square\cdots \square(p_{d_{n}}|_{[a,b]^{d_{n}}}),\]

i.e., the parallelizations of the product functions \(p_{d_{i}}\).

### Main results

In the following we show how to approximate certain compositions of parallelized functions by DNNs without the curse of dimensionality. Our results are somewhat similar to the previous results in Cheridito et al. [4] and Beneventano et al. [3]. While the authors of [4] use the general framework of catalog networks, our arguments exploit the compositional structure of the target functions more directly. While some of
our arguments rely on the results in [3], a main improvement is that we consider compositions of a variable and potentially unbounded number of functions. Specifically, in our first main result, Theorem 1.1 below, the number \(\mathbf{k}(d)\) of functions in the composition is allowed to grow at most polynomially in the parameter \(d\in\mathbb{N}\) which describes the dimension. An additional improvement in Theorem 1.1 compared to [3] is that the functions \(g_{i}^{d}\) are allowed to be parallelizations of Lipschitz functions of input dimension at most \(c\in\mathbb{N}\) (the class \(\mathscr{P}_{c,1}\)) instead of only \(1\)-dimensional Lipschitz functions.

We now present the precise statement of Theorem 1.1 and, thereafter, illustrate this statement by means of several examples.

**Theorem 1.1**.: _Let \(c\in\mathbb{N}\), for every \(d\in\mathbb{N}\) let \(\mathbf{k}(d),\mathfrak{d}_{1}^{d},\mathfrak{d}_{2}^{d},\ldots,\mathfrak{d}_{ \mathbf{k}(d)+1}^{d}\in[cd^{c}]\), for every \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) let \(Q_{i}^{d}\subseteq[-cd^{c},cd^{c}]^{\mathfrak{d}_{i}^{d}}\) be a \(\mathfrak{d}_{i}^{d}\)-dimensional hypercube and let \(g_{i}^{d}\in C(Q_{i}^{d},\mathbb{R}^{\mathfrak{d}_{i+1}^{d}})\) be a function, assume for every \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) that_

\[g_{i}^{d}\in\mathscr{P}_{c,1}(Q_{i}^{d},1)\cup\mathbf{M}(Q_{i}^{d})\cup \mathbf{P}(Q_{i}^{d}), \tag{1.4}\]

_assume for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)-1]\) that \(g_{i}^{d}(Q_{i}^{d})\subseteq Q_{i+1}^{d}\), assume for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) with \(g_{i}^{d}\in\mathbf{P}(Q_{i}^{d})\) that \(Q_{i}^{d}\subseteq[-\frac{1}{8},\frac{1}{8}]^{\mathfrak{d}_{i}^{d}}\), and for every \(d\in\mathbb{N}\) let \(F_{d}\in C(Q_{1}^{d},\mathbb{R}^{\mathfrak{d}_{\mathbf{k}(d)+1}^{d}})\) satisfy \(F_{d}=g_{\mathbf{k}(d)}^{d}\circ g_{\mathbf{k}(d)-1}^{d}\circ\cdots\circ g_{1} ^{d}\). Then there exists \(K\in\mathbb{N}\) such that for every \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\) there exists \(\Phi\in\mathbf{N}\) such that \(\mathcal{R}(\Phi)\in C(\mathbb{R}^{\mathfrak{d}_{1}^{d}},\mathbb{R}^{ \mathfrak{d}_{\mathbf{k}(d)+1}^{d}})\),_

\[\mathcal{P}(\Phi)\leq Kd^{K}\varepsilon^{-2c},\qquad\text{and}\qquad\forall\, x\in Q_{1}^{d}\colon\|\mathcal{R}(\Phi)(x)-F_{d}(x)\|_{1}\leq\varepsilon. \tag{1.5}\]

The condition (1.4) in Theorem 1.1 asserts that each function \(g_{i}^{d}\) in the composition is either a parallelized Lipschitz function with Lipschitz constant \(1\), a parallelized maximum function, or a parallelized product function of \(\mathfrak{d}_{i}^{d}\leq cd^{c}\) variables. Here we think of \(d\in\mathbb{N}\) as a parameter describing the order of magnitude of the dimensions. A particular case is \(\mathfrak{d}_{1}^{d}=d\) for all \(d\in\mathbb{N}\), so that the target function \(F_{d}\) is defined on a \(d\)-dimensional domain.

We need to assume for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) with \(g_{i}^{d}\in\mathbf{P}(Q_{i}^{d})\) that \(Q_{i}^{d}\subseteq[-\frac{1}{8},\frac{1}{8}]^{\mathfrak{d}_{i}^{d}}\) since only on sufficiently small hypercubes the parallelized product functions in \(\mathbf{P}(Q_{i}^{d})\) can be approximated with Lipschitz constant \(1\). For Lipschitz constants greater than \(1\), the composition could potentially produce exponentially large errors and thus could not be approximated without the curse of dimensionality.

The conclusion of the theorem in (1.5) establishes that each of the functions \(F_{d}\) can be approximated uniformly with accuracy \(\varepsilon\) on the \(\mathfrak{d}_{1}^{d}\)-dimensional hypercube \(Q_{1}^{d}\) by a DNN with ReLU activation using at most \(Kd^{K}\varepsilon^{-2c}\) parameters. Hence the number of parameters grows at most polynomially in \(d\) and the accuracy \(\varepsilon\).

Next let us illustrate the statement of Theorem 1.1 by some examples, which demonstrate several cases of compositions of a number of functions depending on the input dimension.

**Example 1.1**.: A situation where Theorem 1.1 applies is the family of functions

\[[e^{-1},1]^{d}\ni x=(x_{1},x_{2},\ldots,x_{d})\mapsto x_{1}^{x_{2}^{-x_{d}}} \in\mathbb{R},\quad d\in\mathbb{N},\]

which can be written as \(g_{1}^{d}\circ\cdots\circ g_{d-1}^{d}\) where \(g_{i}^{d}\colon[e^{-1},1]^{i+1}\to[e^{-1},1]^{i}\) defined by \(g_{i}^{d}(x_{1},\ldots,x_{i-1},x_{i},x_{i+1})=(x_{1},\ldots,x_{i-1},x_{i}^{x_{ i+1}})\) is an element of \(\mathscr{P}_{2,1}([e^{-1},1]^{i+1},1)\), as can be easily verified. Theorem 1.1 hence implies that these functions can be approximated by DNNs without the curse of dimensionality.

**Example 1.2**.: We can also consider for an arbitrary \(a\in(1,\infty)\) the family of functions

\[[1,a]^{d}\ni x=(x_{1},x_{2},\ldots,x_{d})\mapsto\ln(x_{1}+\ln(x_{2}+\ln(\cdots+ \ln(x_{d}))))\in\mathbb{R},\quad d\in\mathbb{N}.\]
Define \(a_{1}^{d},a_{2}^{d},\ldots,a_{d}^{d}\in(1,\infty)\) by \(a_{d}^{d}=a\) and \(a_{i}^{d}=a_{i+1}^{d}+\ln(a_{i+1}^{d})\) for \(i\in\left[d-1\right]\). It is not hard to see that \(a_{i}^{d}\leq cd^{c}\) for a suitable constant \(c\). Now the functions in question can be written as \(g_{i}^{d}\circ\cdots\circ g_{d-1}^{d}\) where \(g_{i}^{d}\colon[1,a_{i+1}^{d}]^{i+1}\to[1,a_{i}^{d}]^{i}\), defined by \(g_{i}^{d}(x_{1},\ldots,x_{i-1},x_{i},x_{i+1})=(x_{1},\ldots,x_{i-1},x_{i}+\ln( x_{i+1}))\), is an element of \(\mathscr{P}_{2,1}([1,a_{i+1}^{d}]^{i+1},1)\). By Theorem 1.1 these functions can thus be approximated by DNNs without the curse of dimensionality.

**Example 1.3**.: For arbitrary \(a\in(0,\frac{1}{8}]\) we can consider the family of functions

\[[-a,a]^{d^{2}}\ni x=(x_{1},x_{2},\ldots,x_{d^{2}})\mapsto\\ \left(\prod_{i=1}^{d}x_{i}\right)\max\bigl{\{}\max_{j=1}^{d}x_{d+ j},\left(\prod_{k=1}^{d}x_{2d+k}\right)\max\{\max_{l=1}^{d}x_{3d+l},\cdots\} \bigr{\}}\in\mathbb{R},\quad d\in\mathbb{N},\]

which is a composition of \(\leq d\) parallelized maximum and product functions and thus satisfies the conditions of the theorem. For example, if \(d=4\) this is the function

\[(x_{1},\ldots,x_{16})\mapsto x_{1}x_{2}x_{3}x_{4}\max\{x_{5},x_{6},x_{7},x_{8 },x_{9}x_{10}x_{11}x_{12}\max\{x_{13},x_{14},x_{15},x_{16}\}\}.\]

By Theorem 1.1 these functions can thus again be approximated by DNNs without the curse of dimensionality.

In our second main result, Theorem 1.2, the number of functions in the composition is a fixed integer \(k\in\mathbb{N}\), but the Lipschitz constants of the functions in the composition are allowed to depend on the dimension \(d\in\mathbb{N}\). This is also an improvement compared to [3] where the maximal Lipschitz constant is a fixed number independent of \(d\in\mathbb{N}\). Here we allow both the parallelized maximum and product functions in \(\mathbf{M},\mathbf{P}\), as well as the generalized multidimensional maximum and product functions \(\mathfrak{m}_{d},\mathfrak{p}_{d}\).

**Theorem 1.2**.: _Let \(c,k\in\mathbb{N}\), for every \(d\in\mathbb{N}\) let \(\mathfrak{d}_{1}^{d},\mathfrak{d}_{2}^{d},\ldots,\mathfrak{d}_{k+1}^{d}\in[cd ^{c}]\), for every \(d\in\mathbb{N}\), \(i\in[k]\) let \(Q_{i}^{d}\subseteq[-cd^{c},cd^{c}]^{\mathfrak{d}_{i}^{d}}\) be a hypercube and let \(g_{i}^{d}\in C(Q_{i}^{d},\mathbb{R}^{\mathfrak{d}_{i+1}})\) be a function, let \(p\in[1,\infty]\), assume for every \(d\in\mathbb{N}\), \(i\in[k]\) that_

\[g_{i}^{d}\in\mathscr{P}_{c,p}(Q_{i}^{d},cd^{c})\cup\{\mathfrak{m}_{\mathfrak{ d}_{i}^{d}}|_{Q_{i}^{d}}\}\cup\{\mathfrak{p}_{\mathfrak{d}_{i}^{d}}|_{Q_{i}^{d}}\} \cup\mathbf{M}(Q_{i}^{d})\cup\mathbf{P}(Q_{i}^{d}), \tag{1.6}\]

_assume for all \(d\in\mathbb{N}\), \(i\in[k-1]\) that \(g_{i}^{d}(Q_{i}^{d})\subseteq Q_{i+1}^{d}\), assume for all \(d\in\mathbb{N}\), \(i\in[k]\) with \(g_{i}^{d}\in\mathbf{P}(Q_{i}^{d})\cup\{\mathfrak{p}_{\mathfrak{d}_{i}^{d}}|_{Q_{ i}^{d}}\}\) that \(Q_{i}^{d}\subseteq[-1,1]^{\mathfrak{d}_{i}^{d}}\), and for every \(d\in\mathbb{N}\) let \(F_{d}\in C(Q_{1}^{d},\mathbb{R}^{\mathfrak{d}_{k+1}^{d}})\) satisfy \(F_{d}=g_{k}^{d}\circ g_{k-1}^{d}\circ\cdots\circ g_{1}^{d}\). Then there exists \(K\in\mathbb{N}\) such that for every \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\) there exists \(\Phi\in\mathbf{N}\) such that \(\mathcal{R}(\Phi)\in C(\mathbb{R}^{\mathfrak{d}_{1}^{d}},\mathbb{R}^{ \mathfrak{d}_{k+1}^{d}})\),_

\[\mathcal{P}(\Phi)\leq Kd^{K}\varepsilon^{-2c},\qquad\text{and}\qquad\forall\,x \in Q_{1}^{d}\colon\left\|\mathcal{R}(\Phi)(x)-F_{d}(x)\right\|_{p}\leq\varepsilon. \tag{1.7}\]

Again, we need to assume for all \(d\in\mathbb{N}\), \(i\in[k]\) with \(g_{i}^{d}\in\mathbf{P}(Q_{i}^{d})\cup\{\mathfrak{p}_{\mathfrak{d}_{i}^{d}}|_{Q_ {i}^{d}}\}\) that \(Q_{i}^{d}\subseteq[-1,1]^{\mathfrak{d}_{i}^{d}}\) since on larger hypercubes the multidimensional product functions can only be approximated with a Lipschitz constant growing exponentially in the dimension (cf., e.g., [3, Proposition 6.8]).

Let us also illustrate the statement of Theorem 1.2 by means of a few examples.

**Example 1.4**.: Consider the family of functions

\[[-1,1]^{d}\ni x\mapsto\max\bigl{\{}(x_{1})^{d},(x_{1}x_{2})^{d+1},\ldots,(x_{1 }x_{2}\cdots x_{d})^{2d-1}\bigr{\}}\in\mathbb{R},\quad d\in\mathbb{N},\]

which can be written as a composition of three functions \(g_{3}^{d}\circ g_{2}^{d}\circ g_{1}^{d}\). Here \(g_{1}^{d}=\mathfrak{p}_{d}\colon[-1,1]^{d}\to[-1,1]^{d}\) is the extended product function, \(g_{2}^{d}\colon[-1,1]^{d}\to[-1,1]^{d}\) is the parallelization of the component-wise functions \([-1,1]\ni y_{i}\mapsto(y_{i})^{d+i-1}\in\mathbb{R}\) which have a Lipschitz constant that grows polynomially in the dimension \(d\), and \(g_{3}^{d}=m_{d}\colon[-1,1]^{d}\to\mathbb{R}\) is the maximum function. Theorem 1.2 thus implies that these functions can be approximated by DNNs without the curse of dimensionality.
**Example 1.5**.: Consider for arbitrary \(c\in\mathbb{N}\) the family of functions

\[[-cd^{c},cd^{c}]^{d}\ni x\mapsto\prod_{i=1}^{d}\exp(-i|x_{i}|^{2})\in\mathbb{R}, \quad d\in\mathbb{N},\]

which is the composition of the product function \(p_{d}\) and the parallelization of the one-dimensional functions \(x_{i}\mapsto\exp(-i|x_{i}|^{2})\) which have a Lipschitz constant bounded by a polynomial in \(d\) and map into the interval \([0,1]\). By Theorem 1.2 these functions can thus be approximated by DNNs without the curse of dimensionality.

**Example 1.6**.: Consider for arbitrary \(c\in\mathbb{N}\) the family of functions

\[[-cd^{c},cd^{c}]^{3d}\ni x\mapsto\max_{l=1}^{d}\cos(lx_{3l-2}+l^{2}x_{3l-1}+l ^{3}x_{3l})\in\mathbb{R},\quad d\in\mathbb{N},\]

which can again be approximated by DNNs without the curse of dimensionality by Theorem 1.2, since the functions \(\mathbb{R}^{3}\ni(y_{1},y_{2},y_{3})\mapsto\cos(ly_{1}+l^{2}y_{2}+l^{3}y_{3}) \in\mathbb{R}\), \(1\leq l\leq d\), have a Lipschitz constant bounded by a polynomial in \(d\).

The above examples illustrate the type of compositional functions that can now be approximated by DNNs with number of parameters growing at most polynomially in the input dimension and the approximation accuracy.

The remainder of this article is organized as follows. In Section 2 we establish abstract DNN approximation results for certain function compositions. Afterwards, in Section 3 we prove that under suitable assumptions the parallelized Lipschitz, product, and maximum functions introduced above can be approximated without the curse of dimensionality. We then combine this with the abstract results from Section 2 to establish the main theorems.

## 2. DNN approximation of composite functions

Throughout this section we employ the notation introduced in Subsection 1.2. The main results of this section are the two abstract approximation results for compositions of functions in Propositions 2.9 and 2.10 which cover the cases of a polynomially growing number of functions with Lipschitz constant \(1\) and of a fixed number of functions with polynomially growing Lipschitz constants, respectively. To prove these we require some technical preparations.

### DNN approximation cost

We first define in Definition 2.1 our version of the approximation cost of continuous functions by DNNs and then establish some basic properties of the approximation cost. Definition 2.1 is inspired by Beneventano et al. [3, Definition 3.2], but is in a sense more general since it allows us to consider different \(\ell_{p}\)-norms on \(\mathbb{R}^{n}\).

**Definition 2.1** (Cost of DNN approximations).: For every \(p\in[1,\infty]\), \(m,n\in\mathbb{N}\), \(D\subseteq\mathbb{R}^{m}\), \(f\in C(D,\mathbb{R}^{n})\), \(L,\varepsilon\in[0,\infty)\) we denote by \(\mathrm{Cost}_{p}(f,L,\varepsilon)\in\mathbb{N}\cup\{\infty\}\) the extended real number given by

\[\begin{split}\mathrm{Cost}_{p}(f,L,\varepsilon)&=\min \Big{(}\Big{\{}N\in\mathbb{N}\colon\exists\,\Phi\in\mathbf{N}\colon\big{[}( \mathcal{R}(\Phi)\in C(\mathbb{R}^{m},\mathbb{R}^{n}))\\ &\wedge(N=\mathcal{P}(\Phi))\wedge\big{(}\sup_{x\in D}\lVert \mathcal{R}(\Phi)(x)-f(x)\rVert_{p}\leq\varepsilon\big{)}\\ &\wedge\big{(}\forall\,x,y\in D\colon\lVert\mathcal{R}(\Phi)(x)- \mathcal{R}(\Phi)(y)\rVert_{p}\leq L\lVert x-y\rVert_{p}\big{)}\Big{]}\Big{\}} \cup\{\infty\}\Big{)}.\end{split} \tag{2.1}\]

That is, \(\mathrm{Cost}_{p}(f,L,\varepsilon)\) is the minimal number of parameters of a DNN which can approximate \(f\) up to accuracy \(\varepsilon\) in the \(\ell_{p}\)-norm while being \(L\)-Lipschitz on the domain of \(f\) with respect to the \(\ell_{p}\)-norm. If such a DNN does not exist then the cost is defined to be infinite. Controlling the Lipschitz constant will be important when estimating the propagation of the approximation error through compositions; see Proposition 2.6 below.
We next restate in Lemma 2.2 below the monotonicity of the approximation cost with respect to the parameters \(L,\varepsilon\) and the domain \(D\), which was established, e.g., in [3, Lemma 3.8] for the case \(p=2\). The case of general \(p\) is entirely analogous.

**Lemma 2.2**.: _Let \(p\in[1,\infty]\), \(m,n\in\mathbb{N}\), \(D\subseteq\mathbb{R}^{m}\), \(E\subseteq D\), \(f\in C(D,\mathbb{R}^{n})\), \(L_{1},L_{2},\varepsilon_{1},\varepsilon_{2}\in[0,\infty)\) satisfy \(L_{1}\leq L_{2}\) and \(\varepsilon_{1}\leq\varepsilon_{2}\). Then_

\[\operatorname{Cost}_{p}(f,L_{1},\varepsilon_{1})\geq\operatorname{Cost}_{p}(f| _{E},L_{2},\varepsilon_{2}). \tag{2.2}\]

In the next lemma we show for arbitrary \(p,q\in[1,\infty]\) how to estimate the cost with respect to the \(\ell_{q}\)-norm against the cost with respect to the \(\ell_{p}\)-norm. For this we need to rescale the Lipschitz constant \(L\) and the approximation accuracy \(\varepsilon\) by factors depending on the input and output dimensions \(m,n\).

**Lemma 2.3** (Cost with respect to different norms).: _Let \(p,q\in[1,\infty]\), \(m,n\in\mathbb{N}\), \(D\subseteq\mathbb{R}^{m}\), \(f\in C(D,\mathbb{R}^{n})\), \(L,\varepsilon\in[0,\infty)\). Then_

\[\operatorname{Cost}_{q}\bigl{(}f,\max\bigl{\{}m^{\nicefrac{{1}}{{p-1}}\!/_{q }},n^{\nicefrac{{1}}{{q-1}}\!/_{p}}\bigr{\}}L,\max\bigl{\{}n^{\nicefrac{{1}}{ {q-1}}\!/_{p}},1\bigr{\}}\varepsilon\bigr{)}\leq\operatorname{Cost}_{p}(f,L, \varepsilon). \tag{2.3}\]

In Lemma 2.3 above we use the convention that \(\frac{1}{\infty}=0\).

Proof of Lemma 2.3.: Throughout this proof we use the well-known fact that for all \(k\in\mathbb{N}\), \(x\in\mathbb{R}^{k}\), \(1\leq s\leq t\leq\infty\) it holds that \(\|x\|_{t}\leq\|x\|_{s}\leq k^{\nicefrac{{1}}{{s-1}}\!/t}\|x\|_{t}\). Assume w.l.o.g. that \(\operatorname{Cost}_{p}(f,L,\varepsilon)<\infty\). (2.1) therefore assures that there exists \(\Phi\in\mathbf{N}\) which satisfies

\[\mathcal{R}(\Phi)\in C(\mathbb{R}^{m},\mathbb{R}^{n}),\qquad \forall\,x\in D\colon\|\mathcal{R}(\Phi)(x)-f(x)\|_{p}\leq\varepsilon,\] \[\forall\,x,y\in D\colon\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y )\|_{p}\leq L\|x-y\|_{p},\qquad\text{and}\qquad\mathcal{P}(\Phi)=\operatorname {Cost}_{p}(f,L,\varepsilon).\]

This yields for all \(x\in D\) that

\[\|\mathcal{R}(\Phi)(x)-f(x)\|_{q}\leq\max\bigl{\{}n^{\nicefrac{{1}}{{q-1}}\! /_{p}},1\bigr{\}}\|\mathcal{R}(\Phi)(x)-f(x)\|_{p}\leq\max\bigl{\{}n^{ \nicefrac{{1}}{{q-1}}\!/_{p}},1\bigr{\}}\varepsilon.\]

Furthermore, if \(q\geq p\) we obtain for all \(x,y\in D\) that

\[\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{q} \leq\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{p}\leq L\|x-y \|_{p}\] \[\leq m^{\nicefrac{{1}}{{p-1}}\!/_{q}}L\|x-y\|_{q}.\]

On the other hand, if \(q\leq p\) we get for all \(x,y\in D\) that

\[\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{q} \leq n^{\nicefrac{{1}}{{q-1}}\!/_{p}}\|\mathcal{R}(\Phi)(x)- \mathcal{R}(\Phi)(y)\|_{p}\leq n^{\nicefrac{{1}}{{q-1}}\!/_{p}}L\|x-y\|_{p}\] \[\leq n^{\nicefrac{{1}}{{q-1}}\!/_{p}}L\|x-y\|_{q}.\]

In any case, we have \(\forall\,x,y\in D\colon\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{q}\leq \max\{m^{\nicefrac{{1}}{{p-1}}\!/_{q}},n^{\nicefrac{{1}}{{q-1}}\!/_{p}}\}L\|x -y\|_{q}\). The proof of Lemma 2.3 is thus complete. 

**Remark 2.4**.: Note that a particularly simple case of Lemma 2.3 arises if \(n=1\), i.e. the output dimension of the considered functions is \(1\), since then all \(\ell_{p}\)-norms on the output space agree. In this case, we obtain

\[\operatorname{Cost}_{q}\bigl{(}f,\max\bigl{\{}m^{\nicefrac{{1}}{{p-1}}\!/_{ q}},1\bigr{\}}L,\varepsilon\bigr{)}\leq\operatorname{Cost}_{p}(f,L,\varepsilon).\]

In particular, if \(p\geq q\) we simply get \(\operatorname{Cost}_{q}(f,L,\varepsilon)\leq\operatorname{Cost}_{p}(f,L,\varepsilon)\).

We next establish in Lemma 2.5 an auxiliary result which shows that if the values of a function are contained in a hypercube \(Q\), the output values of the approximating DNN can be clipped to be contained in \(Q\) as well with only a moderate increase in the number of parameters. This result will be useful when composing multiple DNNs. Lemma 2.5 is a generalization of [3, Lemma 3.7], which covers the case \(p=2\) and \(Q=[-R,R]^{n}\). The proof is very similar.
**Lemma 2.5**.: _Let \(p\in[1,\infty]\), \(m,n\in\mathbb{N}\), \(D\subseteq\mathbb{R}^{m}\), \(f\in C(D,\mathbb{R}^{n})\), \(L,\varepsilon\in[0,\infty)\) satisfy \(\operatorname{Cost}_{p}(f,L,\varepsilon)<\infty\), let \(Q\subseteq\mathbb{R}^{n}\) be a hypercube, and assume \(f(D)\subseteq Q\). Then there exists \(\Phi\in\mathbf{N}\) which satisfies_

(2.4) \[\mathcal{R}(\Phi)\in C(\mathbb{R}^{m},\mathbb{R}^{n}),\qquad \forall\,x\in D\colon\mathcal{R}(\Phi)(x)\in Q,\] \[\forall\,x\in D\colon\|\mathcal{R}(\Phi)(x)-f(x)\|_{p}\leq \varepsilon,\qquad\forall\,x,y\in D\colon\|\mathcal{R}(\Phi)(x)-\mathcal{R}( \Phi)(y)\|_{p}\leq L\|x-y\|_{p},\] \[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \qquad
Combining (2.7) with Lemma 2.5 implies that there exist \(\Phi_{i}\in\mathbf{N}\), \(i\in[n]\), which satisfy for all \(i\in[n]\) that

\[\mathcal{R}(\Phi_{i})\in C(\mathbb{R}^{d_{i}},\mathbb{R}^{d_{i+1}}), \qquad\forall\,x\in Q_{i}\colon\,\mathcal{R}(\Phi_{i})(x)\in Q_{i+1},\] \[\qquad\forall\,x\in Q_{i}\colon\,\|\mathcal{R}(\Phi_{i})(x)-f_{i} (x)\|_{p}\leq\varepsilon n^{-1}(\prod_{j=i+1}^{n}L_{j})^{-1}\|x-y\|_{p},\] \[\qquad\forall\,x,y\in Q_{i}\colon\,\|\mathcal{R}(\Phi_{i})(x)- \mathcal{R}(\Phi_{i})(y)\|_{p}\leq L_{i}\|x-y\|_{p},\] \[\qquad\text{and}\qquad\mathcal{P}(\Phi_{i})=\operatorname{Cost}_ {p}\bigl{(}f_{i},L_{i},\varepsilon n^{-1}(\prod_{j=i+1}^{n}L_{j})^{-1}\bigr{)} +2d_{i+1}(d_{i+1}+1). \tag{2.8}\]

Now define \(\Phi\in\mathbf{N}\) as the composition \(\Phi=\Phi_{n}\circ\mathbf{I}_{d_{n}}\circ\Phi_{n-1}\cdots\circ\mathbf{I}_{d_{2 }}\circ\Phi_{1}\). Here \(\mathbf{I}_{d_{i}}\in\mathbf{N}\) denotes a suitable identity network for \(\mathbb{R}^{d_{i}}\), i.e., it satisfies \(\forall\,x\in\mathbb{R}^{d_{i}}\colon\mathcal{R}(\mathbf{I}_{d_{i}})(x)=x\) (cf., e.g., [3, Definition 2.12]). Observe that [3, Proposition 2.19] and (2.8) imply that

\[\mathcal{P}(\Phi)\leq 3\sum\limits_{i=1}^{n}\mathcal{P}(\Phi_{i})\leq 6\sum \limits_{i=2}^{n}d_{i}(d_{i}+1)+3\sum\limits_{i=1}^{n}\operatorname{Cost}_{p} \bigl{(}f_{i},L_{i},\varepsilon n^{-1}(\prod_{j=i+1}^{n}L_{j})^{-1}\bigr{)}.\]

Furthermore, we have \(\mathcal{R}(\Phi)=\mathcal{R}(\Phi_{n})\circ\cdots\circ\mathcal{R}(\Phi_{1})\), and thus \(\mathcal{R}(\Phi)\in C(\mathbb{R}^{d_{1}},\mathbb{R}^{d_{n+1}})\) is Lipschitz continuous with Lipschitz constant \(\prod_{i=1}^{n}L_{i}\). Finally, [3, Lemma 6.5] ensures that

\[\sup_{x\in Q_{i}}\|\mathcal{R}(\Phi)(x)-(f_{n}\circ f_{n-1}\circ \cdots\circ f_{1})(x)\|_{p}\] \[\leq\sum\limits_{i=1}^{n}\Bigl{[}(\prod_{j=i+1}^{n}L_{j}) \varepsilon n^{-1}(\prod_{j=i+1}^{n}L_{j})^{-1}\Bigr{]}=\sum\limits_{i=1}^{n} (\varepsilon n^{-1})=\varepsilon.\]

The proof of Proposition 2.6 is thus complete. 

As a consequence, we obtain in Corollary 2.7 a general result regarding approximations of compositions of functions without the curse of dimensionality.

**Corollary 2.7**.: _Let \(p\in[1,\infty]\), \(n\in\mathbb{N}\), let \(d_{1},d_{2},\ldots,d_{n+1}\in\mathbb{N}\), \(L_{1},L_{2},\ldots,L_{n}\in(0,\infty)\), for every \(i\in[n]\) let \(Q_{i}\subseteq\mathbb{R}^{d_{i}}\) be a hypercube and let \(f_{i}\in C(Q_{i},\mathbb{R}^{d_{i+1}})\) be a function, assume for all \(i\in[n-1]\) that \(f_{i}(Q_{i})\subseteq Q_{i+1}\), let \(\mathfrak{d}=\max\{d_{1},\ldots,d_{n}\}\), \(\mathfrak{L}=\max\{L_{1},\ldots,L_{n},1\}\), and assume that there exists \(c\in\mathbb{N}\) which satisfies for all \(i\in[n]\), \(\delta\in(0,1]\) that \(\operatorname{Cost}_{p}(f_{i},L_{i},\delta)\leq cd_{i}^{c}L_{i}^{c}\delta^{-c}\). Then it holds for all \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}\bigl{(}f_{n}\circ f_{n-1}\circ\cdots\circ f_{1},\prod _{i=1}^{n}L_{i},\varepsilon\bigr{)}\leq 12n\mathfrak{d}^{2}+3cn^{c+1} \mathfrak{d}^{c}\mathfrak{L}^{cn}\varepsilon^{-c}. \tag{2.9}\]

Proof of Corollary 2.7.: Applying Proposition 2.6 and the monotonicity from Lemma 2.2 yields for all \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}\bigl{(}f_{n}\circ f_{n-1}\circ\cdots\circ f _{1},\prod_{i=1}^{n}L_{i},\varepsilon\bigr{)}\] \[\leq 6\sum\limits_{i=2}^{n}d_{i}(d_{i}+1)+3\sum\limits_{i=1}^{n} \operatorname{Cost}_{p}\bigl{(}f_{i},L_{i},\varepsilon n^{-1}(\prod_{j=i+1}^{n} L_{j})^{-1}\bigr{)}\] \[\leq 12n\mathfrak{d}^{2}+3\sum\limits_{i=1}^{n}c\mathfrak{d}^{c}n^ {c}\varepsilon^{-c}\mathfrak{d}^{c(n-i+1)}\leq 12n\mathfrak{d}^{2}+3c\mathfrak{d}^{c}n^ {c+1}\varepsilon^{-c}\mathfrak{d}^{cn}.\]

The proof of Corollary 2.7 is thus complete. 

**Remark 2.8**.: In Corollary 2.7 we want the right-hand side to grow at most polynomially in the dimension \(\mathfrak{d}\). In the case \(\mathfrak{L}=1\), i.e. \(\max\{L_{1},\ldots,L_{n}\}\leq 1\), the number \(n\) of functions in the composition is allowed to grow polynomially in \(\mathfrak{d}\), i.e., we can have \(n\leq c\mathfrak{d}^{c}\) for some constant \(c\in\mathbb{N}\). If the maximal Lipschitz constant \(\mathfrak{L}\) is larger than \(1\) and the number \(n\) of functions in the composition is a fixed constant we will also obtain an upper bound that avoids the curse of dimensionality.
### Abstract approximation results without the curse of dimensionality

In this subsection we establish two abstract approximation results for composite functions from which Theorems 1.1 and 1.2 in the introduction will follow. Both Proposition 2.9 and Proposition 2.10 are simple consequences of Corollary 2.7. First, in Proposition 2.9 we consider a composition of \(\mathcal{O}(d^{c})\) functions, where \(d\in\mathbb{N}\) is a dimensionality parameter, each of which can be approximated with Lipschitz constant \(1\) without the curse of dimensionality.

**Proposition 2.9**.: _Let \(c\in\mathbb{N}\), \(p\in[1,\infty]\), for every \(d\in\mathbb{N}\) let \(\mathfrak{d}_{1}^{d},\mathfrak{d}_{2}^{d},\ldots,\mathfrak{d}_{\mathbf{k}(d) +1}^{d}\in[d^{c}]\) and \(\mathbf{k}(d)\in[cd^{c}]\), for every \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) let \(Q_{i}^{d}\subseteq\mathbb{R}^{\mathfrak{d}_{i}^{d}}\) be a \(\mathfrak{d}_{i}^{d}\)-dimensional hypercube and let \(g_{i}^{d}\in C(Q_{i}^{d},\mathbb{R}^{\mathfrak{d}_{i+1}^{d}})\) be a function, assume for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\), \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}(g_{i}^{d},1,\varepsilon)\leq cd^{c}\varepsilon^{-c},\]

_assume for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)-1]\) that \(g_{i}^{d}(Q_{i}^{d})\subseteq Q_{i+1}^{d}\), and for every \(d\in\mathbb{N}\) let \(F_{d}\in C(Q_{1}^{d},\mathbb{R}^{\mathfrak{d}_{(d)+1}^{d}})\) satisfy \(F_{d}=g_{\mathbf{k}(d)}^{d}\circ g_{\mathbf{k}(d)-1}^{d}\circ\cdots\circ g_{1} ^{d}\). Then there exists \(K\in\mathbb{N}\) such that for every \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\) there exists \(\Phi\in\mathbf{N}\) such that \(\mathcal{R}(\Phi)\in C(\mathbb{R}^{\mathfrak{d}_{1}^{d}},\mathbb{R}^{ \mathfrak{d}_{(d)+1}^{d}})\),_

\[\mathcal{P}(\Phi)\leq Kd^{K}\varepsilon^{-c},\qquad\text{and}\qquad\forall\,x \in Q_{1}^{d}\colon\|\mathcal{R}(\Phi)(x)-F_{d}(x)\|_{p}\leq\varepsilon. \tag{2.10}\]

Proof of Proposition 2.9.: For every \(d\in\mathbb{N}\), applying Corollary 2.7 (with \(L_{i}\curvearrowright 1\), \(n\curvearrowright\mathbf{k}(d)\), \(d_{i}\curvearrowright\mathfrak{d}_{i}^{d}\)) yields for all \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}(F_{d},1,\varepsilon) =\operatorname{Cost}_{p}(g_{\mathbf{k}(d)}^{d}\circ g_{\mathbf{k} (d)-1}^{d}\circ\cdots\circ g_{1}^{d},1,\varepsilon)\] \[\leq 12\mathbf{k}(d)d^{2c}+3c(\mathbf{k}(d))^{c+1}d^{c^{2}} \varepsilon^{-c}\] \[\leq 12cd^{3c}+3c^{c+2}d^{c(2c+1)}\varepsilon^{-c}\leq 15c^{c+2}d^{c(2 c+1)}\varepsilon^{-c}.\]

The proof of Proposition 2.9 is thus complete. 

Next, in Proposition 2.10 we consider compositions of a constant number \(k\in\mathbb{N}\) of functions, each of which can be approximated with Lipschitz constant \(\mathcal{O}(d^{c})\) without the curse of dimensionality.

**Proposition 2.10**.: _Let \(c,k\in\mathbb{N}\), \(p\in[1,\infty]\), for every \(d\in\mathbb{N}\) let \(\mathfrak{d}_{1}^{d},\mathfrak{d}_{2}^{d},\ldots,\mathfrak{d}_{k+1}^{d}\in[d^ {c}]\), for every \(d\in\mathbb{N}\), \(i\in[k]\) let \(Q_{i}^{d}\subseteq\mathbb{R}^{\mathfrak{d}_{i}^{d}}\) be a \(\mathfrak{d}_{i}^{d}\)-dimensional hypercube and let \(g_{i}^{d}\in C(Q_{i}^{d},\mathbb{R}^{\mathfrak{d}_{i+1}^{d}})\) be a function, assume for all \(d\in\mathbb{N}\), \(i\in[k]\), \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}(g_{i}^{d},cd^{c},\varepsilon)\leq cd^{c}\varepsilon^{-c},\]

_assume for all \(d\in\mathbb{N}\), \(i\in[k-1]\) that \(g_{i}^{d}(Q_{i}^{d})\subseteq Q_{i+1}^{d}\), and for every \(d\in\mathbb{N}\) let \(F_{d}\in C(Q_{1}^{d},\mathbb{R}^{\mathfrak{d}_{k+1}^{d}})\) satisfy \(F_{d}=g_{k}^{d}\circ g_{k-1}^{d}\circ\cdots\circ g_{1}^{d}\). Then there exists \(K\in\mathbb{N}\) such that for every \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\) there exists \(\Phi\in\mathbf{N}\) such that \(\mathcal{R}(\Phi)\in C(\mathbb{R}^{\mathfrak{d}_{1}^{d}},\mathbb{R}^{\mathfrak{ d}_{k+1}^{d}})\),_

\[\mathcal{P}(\Phi)\leq Kd^{K}\varepsilon^{-c},\qquad\text{and}\qquad\forall\,x \in Q_{1}^{d}\colon\|\mathcal{R}(\Phi)(x)-F_{d}(x)\|_{p}\leq\varepsilon. \tag{2.11}\]

Proof of Proposition 2.10.: For every \(d\in\mathbb{N}\), applying Corollary 2.7 (with \(L_{i}\curvearrowright cd^{c}\), \(n\curvearrowright k\), \(d_{i}\curvearrowright\mathfrak{d}_{i}^{d}\)) shows for all \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}(F_{d},(cd^{c})^{k},\varepsilon) =\operatorname{Cost}_{p}(g_{k}^{d}\circ g_{k-1}^{d}\circ\cdots \circ g_{1}^{d},(cd^{c})^{k},\varepsilon)\] \[\leq 12kd^{2c}+3ck^{c+1}d^{c^{2}}(cd^{c})^{ck}\varepsilon^{-c}\] \[=12kd^{2c}+3c^{ck+1}k^{c+1}d^{c^{2}(1+k)}\varepsilon^{-c}\leq 15 k^{c+1}c^{ck+1}d^{c^{2}(1+k)}\varepsilon^{-c}.\]

The proof of Proposition 2.10 is thus complete.
## 3. DNN approximation of specific function classes

In this section we establish approximation results for the specific functions introduced in Subsection 1.2, which allows us to apply Propositions 2.9 and 2.10 to these functions. At the end of this section we employ our approximation results to prove Theorems 1.1 and 1.2 from the introduction.

### DNN approximations of parallelizations

The first step is to show in Lemma 3.2 how parallelizations of the form \(f_{1}\square f_{2}\square\cdots\square f_{n}\), as defined in Subsection 1.2, can be approximated efficiently by DNNs. For this we employ the parallelized DNN architecture from Cheridito et al. [4], which allows one to approximate parallelizations efficiently. Specifically, we use Lemma 3.1 below, which is a reformulation of [4, Proposition 5] in the ReLU case, where \(c=2\) (in the notation of [4, Proposition 5]).

**Lemma 3.1**.: _Let \(n\in\mathbb{N}\), \(\Phi_{1},\ldots,\Phi_{n}\in\mathbf{N}\). Then there exists \(\Phi\in\mathbf{N}\) which satisfies \(\mathcal{R}(\Phi)=\mathcal{R}(\Phi_{1})\square\cdots\square\mathcal{R}(\Phi_ {n})\) and_

\[\mathcal{P}(\Phi)\leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}\max\{\mathcal{I}( \Phi_{i}),\mathcal{O}(\Phi_{i})\}\big{)}^{2}\sum\limits_{i=1}^{n}\mathcal{P}( \Phi_{i}). \tag{3.1}\]

**Lemma 3.2**.: _Let \(p\in[1,\infty]\), \(n\in\mathbb{N}\), \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(L,\varepsilon\in[0,\infty)\), \(d_{1},\ldots,d_{n}\), \(e_{1},\ldots,e_{n}\in\mathbb{N}\), and for every \(i\in[n]\) let \(f_{i}\in C([a,b]^{d_{i}},\mathbb{R}^{e_{i}})\). Then_

\[\mathrm{Cost}_{p}(f_{1}\square f_{2}\square\cdots\square f_{n},L,\varepsilon) \leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}\max\{d_{i},e_{i}\}\big{)}^{2}\sum \limits_{i=1}^{n}\mathrm{Cost}_{p}\big{(}f_{i},L,n^{-\nicefrac{{1}}{{p}}} \varepsilon\big{)}. \tag{3.2}\]

Proof of Lemma 3.2.: Throughout this proof assume without loss of generality that

\[\forall\,i\in[n]\colon\,\mathrm{Cost}_{p}\big{(}f_{i},L,n^{-\nicefrac{{1}}{{ p}}}\varepsilon\big{)}<\infty. \tag{3.3}\]

Note that (3.3) and (2.1) imply that there exist \(\Phi_{i}\in\mathbf{N}\), \(i\in[n]\), which satisfy for all \(i\in[n]\) that

\[\mathcal{R}(\Phi_{i})\in C(\mathbb{R}^{d_{i}},\mathbb{R}^{e_{i}}),\qquad\forall\,x\in[a,b]^{d_{i}}\colon\|\mathcal{R}(\Phi_{i})(x)-f_{i}(x)\| _{p}\leq\varepsilon n^{-\nicefrac{{1}}{{p}}},\] \[\forall\,x,y\in[a,b]^{d_{i}}\colon\|\mathcal{R}(\Phi_{i})(x)- \mathcal{R}(\Phi_{i})(y)\|_{p}\leq L\|x-y\|_{p},\] \[\text{and}\qquad\mathcal{P}(\Phi_{i})=\mathrm{Cost}_{p}\big{(}f_{i },L,\varepsilon n^{-\nicefrac{{1}}{{p}}}\big{)}.\]

Let \(\Phi\in\mathbf{N}\) be the parallelization of \(\Phi_{1},\ldots,\Phi_{n}\) given by Lemma 3.1. That is, we have \(\mathcal{R}(\Phi)=\mathcal{R}(\Phi_{1})\square\cdots\square\mathcal{R}(\Phi_ {n})\in C(\mathbb{R}^{\sum_{i=1}^{n}d_{i}},\mathbb{R}^{\sum_{i=1}^{n}e_{i}})\) and

\[\mathcal{P}(\Phi) \leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}\max\{d_{i},e_{i}\} \big{)}^{2}\sum\limits_{i=1}^{n}\mathcal{P}(\Phi_{i})\] \[=\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}\max\{d_{i},e_{i}\} \big{)}^{2}\sum\limits_{i=1}^{n}\mathrm{Cost}_{p}(f_{i},L,n^{-\nicefrac{{1}}{{ p}}}\varepsilon).\]

We now consider two cases depending on whether \(p\in[1,\infty)\) or \(p=\infty\).

**Case 1.** Assume \(p<\infty\). Thus we get for all \(x=(x_{1},\ldots,x_{n})\in[a,b]^{\sum_{i=1}^{n}d_{i}}\) with \(\forall\,i\in[n]\colon x_{i}\in[a,b]^{d_{i}}\) that

\[\|\mathcal{R}(\Phi)(x)-(f_{1}\square f_{2}\square\cdots\square f_{n})(x)\|_{p}^ {p}=\sum\limits_{i=1}^{n}\|\mathcal{R}(\Phi_{i})(x_{i})-f_{i}(x_{i})\|_{p}^{p} \leq n(\varepsilon n^{-\nicefrac{{1}}{{p}}})^{p}=\varepsilon^{p}.\]

In addition, for all \(x=(x_{1},\ldots,x_{n})\), \(y=(y_{1},\ldots,y_{n})\in[a,b]^{\sum_{i=1}^{n}d_{i}}\) with \(\forall\,i\in[n]\colon x_{i},y_{i}\in[a,b]^{d_{i}}\) we obtain that

\[\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{p}^{p} =\sum\limits_{i=1}^{n}\|\mathcal{R}(\Phi_{i})(x_{i})-\mathcal{R}( \Phi_{i})(y_{i})\|_{p}^{p}\leq L^{p}\sum\limits_{i=1}^{n}\|x_{i}-y_{i}\|_{p}^ {p}\] \[=L^{p}\|x-y\|_{p}^{p}\]
and hence \(\mathcal{R}(\Phi)\) is indeed \(L\)-Lipschitz on \([a,b]^{\sum_{i=1}^{n}d_{i}}\) with respect to \(\|\cdot\|_{p}\).

**Case 2**.: Assume \(p=\infty\). Then we get for all \(x=(x_{1},\ldots,x_{n})\in[a,b]^{\sum_{i=1}^{n}d_{i}}\) with \(\forall\,i\in[n]\colon x_{i}\in[a,b]^{d_{i}}\) that

\[\|\mathcal{R}(x)-(f_{1}\square f_{2}\square\cdots\square f_{n})(x)\|_{\infty} =\max_{i\in[n]}\|\mathcal{R}(\Phi_{i})(x_{i})-f_{i}(x_{i})\|_{\infty}\leq\varepsilon.\]

In addition, for all \(x=(x_{1},\ldots,x_{n})\), \(y=(y_{1},\ldots,y_{n})\in[a,b]^{\sum_{i=1}^{n}d_{i}}\) with \(\forall\,i\in[n]\colon x_{i},y_{i}\in[a,b]^{d_{i}}\) we obtain that

\[\|\mathcal{R}(\Phi)(x)-\mathcal{R}(\Phi)(y)\|_{\infty} =\max_{i\in[n]}\|\mathcal{R}(\Phi_{i})(x_{i})-\mathcal{R}(\Phi_{ i})(y_{i})\|_{\infty}\] \[\leq L\max_{i\in[n]}\|x_{i}-y_{i}\|_{\infty}=L\|x-y\|_{\infty}\]

and thus \(\mathcal{R}(\Phi)\) is indeed \(L\)-Lipschitz with respect to \(\|\cdot\|_{\infty}\).

This completes the proof of Lemma 3.2. 

### DNN approximations of parallelized Lipschitz functions

We next state the essentially known result that every Lipschitz continuous function on a compact set in \(\mathbb{R}^{d}\) can be approximated with error \(\varepsilon>0\) using at most \(\mathcal{O}(\varepsilon^{-2d})\) parameters. While this rate is not optimal (cf., e.g., Shen et al. [33]), it is also important for our purposes to control the Lipschitz constant of the approximating DNN realization itself, which does not directly follow from the optimal bounds in the literature. The proof of Proposition 3.3 uses the results from [16] and Lemma 2.3.

**Proposition 3.3**.: _Let \(d\in\mathbb{N}\). Then there exists \(K\in\mathbb{N}\) which satisfies for all \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(L\in[0,\infty)\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\), and \(f\colon[a,b]^{d}\to\mathbb{R}\) with \(\forall\,x,y\in[a,b]^{d}\colon|f(x)-f(y)|\leq L\|x-y\|_{p}\) that_

\[\operatorname{Cost}_{p}\bigl{(}f,d^{1-\nicefrac{{1}}{{p}}}L,\varepsilon \bigr{)}\leq K(\max\{L(b-a),1\})^{2d}\varepsilon^{-2d}. \tag{3.4}\]

Proof of Proposition 3.3.: First observe that for all \(u\in\mathbb{R}^{d}\), \(p\in[1,\infty]\) we have \(\|u\|_{p}\leq\|u\|_{1}\). Hence, [16, Corollary 4.9 and Eq. (4.38)] show that there exists \(K\in\mathbb{N}\) which satisfies for all \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(L\in[0,\infty)\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\), and \(f\colon[a,b]^{d}\to\mathbb{R}\) with \(\forall\,x,y\in[a,b]^{d}\colon|f(x)-f(y)|\leq L\|x-y\|_{p}\leq L\|x-y\|_{1}\) that1

Footnote 1: The Lipschitz property of the approximating DNN follows since its realization is given by a maximum convolution; cf. [16, Lemma 3.12 and Proposition 4.4].

\[\operatorname{Cost}_{1}(f,L,\varepsilon)\leq K(\max\{L(b-a),1\})^{2d} \varepsilon^{-2d}.\]

Combining this with Lemma 2.3 demonstrates for all \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(L\in[0,\infty)\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\), and \(f\colon[a,b]^{d}\to\mathbb{R}\) with \(\forall\,x,y\in[a,b]^{d}\colon|f(x)-f(y)|\leq L\|x-y\|_{p}\) that

\[\operatorname{Cost}_{p}(f,d^{1-\nicefrac{{1}}{{p}}}L,\varepsilon)\leq \operatorname{Cost}_{1}(f,L,\varepsilon)\leq K(\max\{L(b-a),1\})^{2d} \varepsilon^{-2d}.\]

This completes the proof of Proposition 3.3. 

Combining this result with Lemma 3.2 we obtain the following general result about parallelized low-dimensional Lipschitz functions with input dimension \(d_{i}\leq k\).

**Corollary 3.4**.: _Let \(k\in\mathbb{N}\), \(L\in[0,\infty)\), \(n\in\mathbb{N}\), \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(p\in[1,\infty]\), \(d_{1},\ldots,d_{n}\in\mathbb{N}\) satisfy \(\max_{i\in[n]}d_{i}\leq k\), and for every \(i\in[n]\) let \(f_{i}\in C([a,b]^{d_{i}},\mathbb{R})\) satisfy \(\forall\,x,y\in[a,b]^{d_{i}}\colon|f_{i}(x)-f_{i}(y)|\leq L\|x-y\|_{p}\). Then there exists \(K\in\mathbb{N}\), depending only on \(k\), which satisfies for all \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}\bigl{(}f_{1}\square f_{2}\square\cdots\square f_{n},k^{1- \nicefrac{{1}}{{p}}}L,\varepsilon\bigr{)}\leq Kn^{2k+3}(\max\{L(b-a),1\})^{2k} \varepsilon^{-2k}. \tag{3.5}\]
Proof of Corollary 3.4.: Note that Proposition 3.3 and Lemma 2.2 imply that there exists \(K\in\mathbb{N}\), depending only on \(k\), which satisfies for all \(i\in[n]\), \(\varepsilon\in(0,1]\) that

\[\mathrm{Cost}_{p}\big{(}f_{i},k^{1-\nicefrac{{1}}{{p}}}L,\varepsilon\big{)}\leq \mathrm{Cost}_{p}\big{(}f_{i},(d_{i})^{1-\nicefrac{{1}}{{p}}}L,\varepsilon\big{)} \leq K(\max\{L(b-a),1\})^{2k}\varepsilon^{-2k}.\]

Hence, Lemma 3.2 demonstrates for all \(\varepsilon\in(0,1]\) that

\[\mathrm{Cost}_{p}\big{(}f_{1}\square f_{2}\square\cdots\square f_{ n},k^{1-\nicefrac{{1}}{{p}}}L,\varepsilon\big{)}\] \[\leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}d_{i}\big{)}^{2}\sum \limits_{i=1}^{n}\mathrm{Cost}_{p}\big{(}f_{i},k^{1-\nicefrac{{1}}{{p}}}L,n^{- \nicefrac{{1}}{{p}}}\varepsilon\big{)}\] \[\leq\tfrac{11}{4}n^{2}k^{2}nK(\max\{L(b-a),1\})^{2k}\varepsilon^ {-2k}n^{2\nicefrac{{1}}{{p}}}\] \[\leq\tfrac{11k^{2}K}{4}n^{2k+3}(\max\{L(b-a),1\})^{2k} \varepsilon^{-2k}.\]

The proof of Corollary 3.4 is thus complete. 

Finally, we restate this result in terms of the parallelized Lipschitz function classes \(\mathcal{G}_{\!k,p}\) as defined above. Note that the required number of parameters grows only polynomially in the input dimension \(d\) for every fixed integer \(k\in\mathbb{N}\).

**Corollary 3.5**.: _Let \(k\in\mathbb{N}\). Then there exists \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(p\in[1,\infty]\), \(L\in[0,\infty)\), \(\varepsilon\in(0,1]\), \(f\in\mathcal{G}_{\!k,p}([a,b]^{d},L)\) that_

\[\mathrm{Cost}_{p}\big{(}f,k^{1-\nicefrac{{1}}{{p}}}L,\varepsilon\big{)}\leq Kd ^{2k+3}(\max\{L(b-a),1\})^{2k}\varepsilon^{-2k}. \tag{3.6}\]

### DNN approximations of products

In this section we state some results on the approximation cost of multidimensional products as defined in (1.2). The first result, Lemma 3.6 below, is a consequence of [3, Proposition 6.8] and Lemma 2.3. Similar approximation results for multidimensional products without the curse of dimensionality can also be found in [4, 32, 35].

**Lemma 3.6**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(a\in[1,\infty)\), \(p\in[1,\infty]\), \(\varepsilon\in(0,\infty)\) that_

\[\mathrm{Cost}_{p}\big{(}p_{d}|_{[-a,a]^{d}},\sqrt{32}d^{3}a^{2d-1},\varepsilon \big{)}\leq Kd^{3}\big{(}1+\ln(a)+\mathfrak{r}(\ln(\varepsilon^{-1}))\big{)}. \tag{3.7}\]

Proof of Lemma 3.6.: Observe that [3, Proposition 6.8] demonstrates that there exists \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(a\in[1,\infty)\), \(\varepsilon\in(0,\infty)\) that

Combining this with Lemma 2.3 and the fact that for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\) it holds that \(d^{\nicefrac{{1}}{{2}}-\nicefrac{{1}}{{p}}}\leq d^{\nicefrac{{1}}{{2}}}\) establishes (3.7). This completes the proof of Lemma 3.6. 

Since the Lipschitz constant in (3.7) grows exponentially in \(d\) for \(a>1\), in the following we restrict to the hypercube \([-1,1]^{d}\). For the parallelized product functions in \(\mathbf{P}([-1,1]^{d})\) we obtain as a consequence the following approximation result.

**Corollary 3.7**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\), \(p\in[1,\infty]\), \(f\in\mathbf{P}([-1,1]^{d})\) that_

\[\mathrm{Cost}_{p}\big{(}f,\sqrt{32}d^{3},\varepsilon\big{)}\leq Kd^{K} \varepsilon^{-1} \tag{3.8}\]

Proof of Corollary 3.7.: Note that Lemma 3.6 ensures that there exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\), \(\varepsilon\in(0,\infty)\) that

\[\mathrm{Cost}_{p}\big{(}p_{d}|_{[-1,1]^{d}},\sqrt{32}d^{3},\varepsilon\big{)} \leq Kd^{3}\big{(}1+\mathfrak{r}(\ln(\varepsilon^{-1}))\big{)}.\]
Combining this with Lemma 3.2 and the fact that \(\forall\,u\in[1,\infty)\colon 1+\ln(u)\leq u\) demonstrates for all \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\), \(d,n,d_{1},d_{2},\ldots,d_{n}\in\mathbb{N}\) with \(\sum_{i=1}^{n}d_{i}=d\) and all \(f=(p_{d_{1}}|_{[-1,1]^{d_{i}}})\square\cdots\square[p_{d_{n}}|_{[-1,1]^{d_{n}}}) \in\mathbf{P}([-1,1]^{d})\) that

\[\operatorname{Cost}_{p}(f,\sqrt{32}d^{3},\varepsilon) \leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}d_{i}\big{)}^{2}\sum_{ i=1}^{n}\operatorname{Cost}_{p}\big{(}p_{d_{i}}|_{[-1,1]^{d_{i}}},\sqrt{32}d^{3}, n^{-\nicefrac{{1}}{{p}}}\varepsilon\big{)}\] \[\leq\tfrac{11}{4}n^{2}d^{2}K\sum_{i=1}^{n}(d_{i})^{3}\big{(}1+\ln (\varepsilon^{-1})+\tfrac{1}{p}\ln n\big{)}\] \[\leq\tfrac{11}{4}n^{2}d^{2}Kd^{3}(1+\ln(\varepsilon^{-1}))(1+\ln n)\] \[\leq\tfrac{11}{4}Kn^{3}d^{5}\varepsilon^{-1}\leq\tfrac{11}{4} Kd^{8}\varepsilon^{-1}.\]

The proof of Corollary 3.7 is thus complete. 

Using the monotonicity in Lemma 2.2, the same approximation result holds for \(f\in\mathbf{P}(Q)\) for any \(d\)-dimensional hypercube \(Q\subseteq[-1,1]^{d}\).

We next turn to the extended product functions \(\mathfrak{p}_{d}\). Combining [3, Corollary 6.9] with Lemma 2.3 we obtain an approximation of \(\mathfrak{p}_{d}\) with respect to arbitrary \(\ell_{p}\)-norms.

**Lemma 3.8**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}\big{(}\mathfrak{p}_{d}|_{[-1,1]^{d}},\sqrt{32}d^{ \nicefrac{{1}}{{2}}},\varepsilon\big{)}\leq Kd^{K}\varepsilon^{-1}. \tag{3.9}\]

Proof of Lemma 3.8.: Observe that [3, Corollary 6.9] implies that there exists \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(a\in[1,\infty)\), \(\varepsilon\in(0,\infty)\) that

Combining this with Lemma 2.3 yields for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\), \(\varepsilon\in(0,\infty)\) that

\[\operatorname{Cost}_{p}\big{(}\mathfrak{p}_{d}|_{[-1,1]^{d}},\sqrt{32}d^{ \nicefrac{{1}}{{2}}},d^{\nicefrac{{1}}{{2}}}\varepsilon\big{)}\leq Kd^{5} \big{(}1+\mathfrak{r}(\ln(\varepsilon^{-1}))\big{)}.\]

Hence, we obtain for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}\big{(}\mathfrak{p}_{d}|_{[-1,1]^{d}}, \sqrt{32}d^{\nicefrac{{1}}{{2}}},\varepsilon\big{)} \leq Kd^{5}\big{(}1+\mathfrak{r}(\ln(d^{\nicefrac{{1}}{{2}}} \varepsilon^{-1}))\big{)}\] \[\leq Kd^{5}(1+\ln(d))(1+\ln(\varepsilon^{-1}))\leq Kd^{6} \varepsilon^{-1}.\]

This establishes (3.9). The proof of Lemma 3.8 is thus complete. 

Again the analogous result holds for \(\mathfrak{p}_{d}|_{Q}\) for any hypercube \(Q\subseteq[-1,1]^{d}\).

### DNN approximations of products with Lipschitz constant 1

In this subsection we show that on smaller cubes of side-length at most \(\tfrac{1}{4}\) we can even approximate the product function \(p_{d}\) with Lipschitz constant \(1\) with respect to arbitrary \(\ell_{p}\)-norms. The proof of Lemma 3.9 is based on [3, Lemma 6.7], which essentially implies the claimed statement for dimensions equal to a power of \(2\). For a general input dimension we use a form of backward induction. If we want to approximate compositions of a polynomially growing number of functions we need the Lipschitz constant to be at most \(1\); cf. Remark 2.8 above.

**Lemma 3.9**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\) that_

\[\operatorname{Cost}_{p}\big{(}p_{d}|_{[-\frac{1}{8},\frac{1}{8}]^{d}},1, \varepsilon\big{)}\leq Kd^{4}\big{(}1+\ln(\varepsilon^{-1})\big{)}. \tag{3.10}\]
Proof of Lemma 3.9.: First, [3, Lemma 6.7] implies that there exists a constant \(K\in\mathbb{N}\) which satisfies for all \(e\in\mathbb{N}\), \(a,\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{2}\bigl{(}p_{2^{e}}|_{[-a,a]^{2^{e}}},2^{5e/2}a^{2^{e-1}}, \varepsilon\bigr{)}\leq K8^{e}\bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}.\]

Combining this with Lemma 2.3 demonstrates for all \(p\in[1,\infty]\), \(e\in\mathbb{N}\), \(a,\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}\bigl{(}p_{2^{e}}|_{[-a,a]^{2^{e}}},2^{3e}a^{2^{e-1}}, \varepsilon\bigr{)}\leq K8^{e}\bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}.\]

Applying this with \(a=\frac{1}{8}\) and \(\varepsilon\curvearrowright8^{-2^{e-1}}\varepsilon\) shows that for all \(p\in[1,\infty]\), \(e\in\mathbb{N}\), \(\varepsilon\in(0,1]\) there exists a network \(\Phi_{e}^{p,\varepsilon}\in\mathbf{N}\) such that

\[\mathcal{R}(\Phi_{e}^{p,\varepsilon})\in C(\mathbb{R}^{2^{e}}, \mathbb{R}),\qquad\forall\,x\in[-\tfrac{1}{8},\tfrac{1}{8}]^{2^{e}}\colon| \mathcal{R}(\Phi_{e}^{p,\varepsilon})-p_{2^{e}}(x)|\leq 8^{-2^{e-1}}\varepsilon,\] \[\qquad\forall\,x,y\in[-\tfrac{1}{8},\tfrac{1}{8}]^{2^{e}}\colon| \mathcal{R}(\Phi_{e}^{p,\varepsilon})(x)-\mathcal{R}(\Phi_{e}^{p,\varepsilon })(y)|\leq 8^{e+1-2^{e}}\|x-y\|_{p},\] \[\text{and}\qquad\mathcal{P}(\Phi_{e}^{p,\varepsilon})\leq K8^{e} \bigl{(}1+\ln(\varepsilon^{-1})+2^{e-1}\ln(8)\bigr{)}\leq(K+\ln(8))16^{e} \bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}. \tag{3.11}\]

Now let \(d\in\mathbb{N}\), assume w.l.o.g. that \(d\geq 3\) (otherwise, \(d\) is a power of \(2\)), and choose \(e\in\mathbb{N}\) with \(2^{e-1}+1\leq d\leq 2^{e}\). Denote by \(A\colon\mathbb{R}^{d}\to\mathbb{R}^{2^{e}}\) the affine linear map defined by

\[A(x_{1},\dots,x_{d})=\bigl{(}x_{1},\dots,x_{d},\tfrac{1}{8},\dots,\tfrac{1}{8 }\bigr{)}\in\mathbb{R}^{2^{e}}.\]

Note that \(A\) maps \([-\tfrac{1}{8},\tfrac{1}{8}]^{d}\) into \([-\tfrac{1}{8},\tfrac{1}{8}]^{2^{e}}\). Given \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\) we denote by \(\Psi_{d}^{p,\varepsilon}\in\mathbf{N}\) the network with realization given by

\[\mathcal{R}(\Psi_{d}^{p,\varepsilon})(x)=8^{2^{e}-d}\mathcal{R}(\Phi_{e}^{p, \varepsilon})(A(x)).\]

In other words, \(\Psi_{d}^{p,\varepsilon}\) is obtained from \(\Phi_{e}^{p,\varepsilon}\) by pre-composition with the affine map \(A\) and post-composition with a scalar multiplication. Hence, [16, Proposition 2.20] implies that \(\mathcal{I}(\Psi_{d}^{p,\varepsilon})=d\leq 2^{e}=\mathcal{I}(\Phi_{e}^{p,\varepsilon})\) and all other layer dimensions are equal, whence

\[\mathcal{P}(\Psi_{d}^{p,\varepsilon})\leq\mathcal{P}(\Phi_{e}^{p,\varepsilon })\leq(K+\ln(8))16^{e}\bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}\leq 16(K+3)d^{4} \bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}.\]

Furthermore, note that (3.11) and the fact that \(p_{2^{e}}(A(x))=8^{d-2^{e}}p_{d}(x)\) show for all \(x,y\in[-\tfrac{1}{8},\tfrac{1}{8}]^{d}\) that

\[|\mathcal{R}(\Psi_{d}^{p,\varepsilon})(x)-p_{d}(x)|=|8^{2^{e}-d}\mathcal{R}( \Phi_{e}^{p,\varepsilon})(A(x))-8^{2^{e}-d}p_{2^{e}}(A(x))|\leq 8^{2^{e}-d}8^{-2^{e-1} }\varepsilon\leq\varepsilon\]

and

\[|\mathcal{R}(\Psi_{d}^{p,\varepsilon})(x)-\mathcal{R}(\Psi_{d}^{ p,\varepsilon}(y))| =8^{2^{e}-d}|\mathcal{R}(\Phi_{e}^{p,\varepsilon})(A(x))- \mathcal{R}(\Phi_{e}^{p,\varepsilon})(A(y))|\] \[\leq 8^{2^{e}-d}8^{e+1-2^{e}}\|A(x)-A(y)\|_{p}=8^{e+1-d}\|x-y\|_{p}\] \[\leq 8^{e-2^{e-1}}\|x-y\|_{p}\leq\|x-y\|_{p}.\]

This completes the proof of Lemma 3.9. 

**Remark 3.10**.: From this proof one can see that the upper bound \(\frac{1}{8}\) is not optimal for high dimensions \(d\). Choosing \(e\) as in the proof, \(a\) can be an arbitrary number in \((0,8^{-e/2^{e-1}}]\) in order for the Lipschitz constant to be at most \(1\). This upper bound approaches \(1\) as \(d\to\infty\) (whence \(e\to\infty\)).

For any hypercube \(Q\subseteq[-\tfrac{1}{8},\tfrac{1}{8}]^{d}\) we thus obtain as a consequence the result in Corollary 3.11 the parallelized product functions in \(\mathbf{P}(Q)\), again using Lemma 3.2.

**Corollary 3.11**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), every \(d\)-dimensional hypercube \(Q\subseteq[-\tfrac{1}{8},\tfrac{1}{8}]^{d}\), and all \(\varepsilon\in(0,1]\), \(p\in[1,\infty]\), \(f\in\mathbf{P}(Q)\) that_

\[\operatorname{Cost}_{p}(f,1,\varepsilon)\leq Kd^{K}\varepsilon^{-1}. \tag{3.12}\]
Proof of Corollary 3.11.: Observe that Lemma 3.9 implies that there exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), every hypercube \(Q=[a,b]^{d}\subseteq[-\frac{1}{8},\frac{1}{8}]^{d}\), and all \(\varepsilon\in(0,1]\), \(p\in[1,\infty]\), that

\[\operatorname{Cost}_{p}\bigl{(}p_{d}|_{Q},1,\varepsilon\bigr{)}\leq Kd^{4} \bigl{(}1+\ln(\varepsilon^{-1})\bigr{)}.\]

Combining this with Lemma 3.2 and the fact that \(\forall\,u\in[1,\infty)\colon 1+\ln(u)\leq u\) shows for all \(p\in[1,\infty]\), \(\varepsilon\in(0,1]\), \(d,n,d_{1},d_{2},\ldots,d_{n}\in\mathbb{N}\) with \(\sum_{i=1}^{n}d_{i}=d\) and all \(f=(p_{d_{1}}|_{[a,b]^{d_{1}}})\square\cdots\square(p_{d_{n}}|_{[a,b]^{d_{n}}}) \in\mathbf{P}(Q)\) that

\[\operatorname{Cost}_{p}(f,1,\varepsilon) \leq\tfrac{11}{4}n^{2}\bigl{(}\max_{i\in[n]}d_{i}\bigr{)}^{2} \sum_{i=1}^{n}\operatorname{Cost}_{p}\bigl{(}p_{d_{i}}|_{[a,b]^{d_{i}}},1,n^{ \nicefrac{{-1}}{{p}}}\varepsilon\bigr{)}\] \[\leq\tfrac{11}{4}n^{2}d^{2}K\sum_{i=1}^{n}(d_{i})^{4}\bigl{(}1+ \ln(\varepsilon^{-1})+\tfrac{1}{p}\ln n\bigr{)}\] \[\leq\tfrac{11}{4}n^{2}d^{2}Kd^{4}(1+\ln(\varepsilon^{-1}))(1+\ln n)\] \[\leq\tfrac{11}{4}Kn^{3}d^{6}\varepsilon^{-1}\leq\tfrac{11}{4} Kd^{9}\varepsilon^{-1}.\]

The proof of Corollary 3.11 is thus complete. 

### DNN approximations of maxima

Our final example of a particular family of functions which can be approximated by DNNs without the curse of dimensionality is given by the multidimensional maximum functions as defined in (1.2). In fact, it is well-known in the scientific literature that these functions can be represented exactly by ReLU DNNs with only polynomially many parameters; cf., e.g., [1, 3, 4, 16]. Using Lemma 2.3 and [3, Proposition 5.4] we derive the following result for an approximation with Lipschitz constant \(1\).

**Lemma 3.12**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), every \(d\)-dimensional hypercube \(Q\), and all \(\varepsilon\in[0,\infty)\), \(p\in[1,\infty]\) that_

\[\operatorname{Cost}_{p}(m_{d}|_{Q},1,\varepsilon)\leq Kd^{2}. \tag{3.13}\]

Proof of Lemma 3.12.: Note that [3, Proposition 5.4] shows that there exist \(K\in\mathbb{N}\) and \(\Phi_{d}\in\mathbf{N}\), \(d\in\mathbb{N}\), which satisfy for all \(d\in\mathbb{N}\), \(x,y\in\mathbb{R}^{d}\) that \(\mathcal{R}(\Phi_{d})\in C(\mathbb{R}^{d},\mathbb{R})\), \(\mathcal{P}(\Phi_{d})\leq Kd^{2}\), \(\mathcal{R}(\Phi_{d})(x)=m_{d}(x)\), and \(|\mathcal{R}(\Phi_{d})(x)-\mathcal{R}(\Phi_{d})(y)|\leq\|x-y\|_{\infty}\). This ensures for all \(d\in\mathbb{N}\), \(\varepsilon\in[0,\infty)\) and every \(Q=[a,b]^{d}\subseteq\mathbb{R}^{d}\) that \(\operatorname{Cost}_{\infty}(m_{d}|_{Q},1,\varepsilon)\leq Kd^{2}\). Combining this with Lemma 2.3 establishes (3.13). This completes the proof of Lemma 3.12. 

Similarly as for the product functions, we get for the parallelized maximum functions in \(\mathbf{M}(Q)\) the following approximation result.

**Corollary 3.13**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), every \(d\)-dimensional hypercube \(Q\subseteq\mathbb{R}^{d}\), and all \(\varepsilon\in[0,\infty)\), \(p\in[1,\infty]\), \(f\in\mathbf{M}(Q)\) that_

\[\operatorname{Cost}_{p}(f,1,\varepsilon)\leq Kd^{K}. \tag{3.14}\]

Proof of Corollary 3.13.: Observe that Lemma 3.12 assures that there exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(Q=[a,b]^{d}\subseteq\mathbb{R}^{d}\), \(\varepsilon\in[0,\infty)\), \(p\in[1,\infty]\) that

\[\operatorname{Cost}_{p}(m_{d}|_{Q},1,\varepsilon)\leq Kd^{2}.\]

Analogously to the proof of Corollary 3.11, we combine this with Lemma 3.2 to obtain for all \(a\in\mathbb{R}\), \(b\in(a,\infty)\), \(p\in[1,\infty]\), \(\varepsilon\in(0,\infty)\), \(d,n,d_{1},d_{2},\ldots,d_{n}\in\mathbb{N}\) with \(\sum_{i=1}^{n}d_{i}=d\)
and all \(f=(m_{d_{1}}|_{[a,b]^{d_{4}}})\square\cdots\square(m_{d_{n}}|_{[a,b]^{d_{n}}})\in \mathbf{M}(Q)\) that

\[\operatorname{Cost}_{p}(f,1,\varepsilon) \leq\tfrac{11}{4}n^{2}\big{(}\max_{i\in[n]}d_{i}\big{)}^{2}\sum_{ i=1}^{n}\operatorname{Cost}_{p}\big{(}m_{d_{i}}|_{[a,b]^{d_{i}}},1,n^{-\nicefrac{{1}}{{ p}}}\varepsilon\big{)}\] \[\leq\tfrac{11}{4}n^{2}d^{2}\sum_{i=1}^{n}K(d_{i})^{2}\leq\tfrac{11 }{4}Kd^{6}.\]

This completes the proof of Corollary 3.13. 

For the extended maximum functions \(\mathfrak{m}_{d}\) we obtain the following result by using [3, Corollary 5.5] and Lemma 2.3. For \(p<\infty\) the Lipschitz constant depends on the dimension, due to the use of the \(\ell_{p}\)-norm on the output space \(\mathbb{R}^{d}\).

**Lemma 3.14**.: _There exists a constant \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), every \(d\)-dimensional hypercube \(Q\subseteq\mathbb{R}^{d}\), and all \(\varepsilon\in[0,\infty)\), \(p\in[1,\infty]\) that_

\[\operatorname{Cost}_{p}\big{(}\mathfrak{m}_{d}|_{Q},d^{\nicefrac{{1}}{{p}}}, \varepsilon\big{)}\leq Kd^{4}. \tag{3.15}\]

Proof of Lemma 3.14.: Note that [3, Corollary 5.5] assures that there exist \(K\in\mathbb{N}\) and \(\Phi_{d}\in\mathbf{N}\), \(d\in\mathbb{N}\), which satisfy for all \(d\in\mathbb{N}\), \(x\in\mathbb{R}^{d}\) that \(\mathcal{R}(\Phi_{d})\in C(\mathbb{R}^{d},\mathbb{R}^{d})\), \(\mathcal{P}(\Phi_{d})\leq Kd^{4}\), and \(\mathcal{R}(\Phi_{d})(x)=\mathfrak{m}_{d}(x)\). Furthermore, observe that \(\mathfrak{m}_{d}\) is \(1\)-Lipschitz with respect to the \(\ell_{\infty}\)-norm. Hence, we obtain for all \(d\in\mathbb{N}\), \(Q=[a,b]^{d}\subseteq\mathbb{R}^{d}\), \(\varepsilon\in[0,\infty)\) that \(\operatorname{Cost}_{\infty}\big{(}\mathfrak{m}_{d}|_{Q},1,\varepsilon\big{)} \leq Kd^{4}\). Combining this with Lemma 2.3 establishes (3.15). The proof of Lemma 3.14 is thus complete. 

### Proof of the main results

Now we have all the ingredients to prove the main theorems from the introduction. We first employ Proposition 2.9 to establish the result in Theorem 1.1 with a polynomial number of functions in the composition.

Proof of Theorem 1.1.: Note that Corollary 3.5 shows that there exists \(K_{1}\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) with \(g_{i}^{d}\in\mathscr{P}_{\varepsilon,1}(Q_{i}^{d},1)\) that

\[\forall\,\varepsilon\in(0,1]\colon\operatorname{Cost}_{1}(g_{i}^{d},1, \varepsilon)\leq K_{1}(\mathfrak{d}_{i}^{d})^{2c+3}(2cd^{c})^{2c}\varepsilon^{ -2c}\leq K_{1}c^{2c+3}(2c)^{2c}d^{c(2c+3)+2c^{2}}\varepsilon^{-2c}.\]

Here we used that Corollary 3.5 can be applied with the side-length \(b-a\leq 2cd^{c}\), since \(Q_{i}^{d}\subseteq[-cd^{c},cd^{c}]^{b_{i}^{d}}\) by assumption. Furthermore, Corollary 3.11 ensures that there exists \(K_{2}\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) with \(g_{i}^{d}\in\mathbf{P}(Q_{i}^{d})\) that

\[\forall\,\varepsilon\in(0,1]\colon\operatorname{Cost}_{1}(g_{i}^{d},1, \varepsilon)\leq K_{2}(\mathfrak{d}_{i}^{d})^{K_{2}}\varepsilon^{-1}\leq K_{2 }c^{K_{2}}d^{K_{2}}\varepsilon^{-2c}.\]

Finally, Corollary 3.13 implies that there exists \(K_{3}\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\) with \(g_{i}^{d}\in\mathbf{M}(Q_{i}^{d})\) that

\[\forall\,\varepsilon\in(0,1]\colon\operatorname{Cost}_{1}(g_{i}^{d},1, \varepsilon)\leq K_{3}(\mathfrak{d}_{i}^{d})^{K_{3}}\leq K_{3}c^{K_{3}}d^{cK_{3 }}\varepsilon^{-2c}.\]

Hence, we obtain for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\), \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{1}(g_{i}^{d},1,\varepsilon)\leq\max\bigl{\{}2^{2c}K_{1}c^{ 4c+3},K_{2}c^{K_{2}},K_{3}c^{K_{3}}\bigr{\}}d^{c\max\{4c+3,K_{2},K_{3}\}} \varepsilon^{-2c}.\]

Combining this with Proposition 2.9 establishes the claim. The proof of Theorem 1.1 is thus complete. 

Next we apply Proposition 2.10 to establish Theorem 1.2, where the Lipschitz constants of the composed functions grow polynomially in the dimension.

Proof of Theorem 1.2.: Analogously to the proof of Theorem 1.1 we can combine (1.6), Corollary 3.5, Corollary 3.7, Lemma 3.8, Corollary 3.13, and Lemma 3.14 to obtain that there exists \(K\in\mathbb{N}\) which satisfies for all \(d\in\mathbb{N}\), \(i\in[\mathbf{k}(d)]\), \(\varepsilon\in(0,1]\) that

\[\operatorname{Cost}_{p}(g_{i}^{d},Kd^{K},\varepsilon)\leq K(\mathfrak{d}_{i}^{d} )^{K}\max\{\varepsilon^{-2c},\varepsilon^{-1},1\}\leq Kd^{K}\varepsilon^{-2c}.\]
Applying the second abstract approximation result in Proposition 2.10 hence establishes the claim. The proof of Theorem 1.2 is thus complete. 

### Acknowledgments

This work has been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy EXC 2044-390685587, Mathematics Munster: Dynamics-Geometry-Structure. Helpful suggestions by Patrick Cheridito, Arnulf Jentzen, Benno Kuckuck, and Florian Rossmannek, in particular regarding Lemma 3.9, are gratefully acknowledged.
