Chapter 7: Expressivity of Feedforward Networks

Having understood the architecture and the training of feedforward neural networks in the previous chapters, we now ask the question

Why should neural networks work?

There is abundant empirical evidence that deep learning models work well in a wide range of domains, such as image recognition and natural language processing. However, empirical evidence does not explain why they work. A part of the answer comes from mathematical results on the capacity of neural networks to approximate functions. This capacity is referred to as the expressivity of a network. In this chapter, we review a few of these results.

A neural network is used in two major ways. One is pattern recognition, which corresponds to a classification problem, as illustrated in the previous chapters. The other is function approximation, in particular regression, where the goal is to approximate an underlying functional relationship between inputs and outputs. In fact, classification can also be viewed as a function approximation, where the function maps input vectors to discrete labels.

In recent years, neural networks have also been used to construct approximate solutions of differential equations. The differential equation is incorporated into the cost function through its residual. Such networks are known as physics-informed neural networks (PINNs). PINNs provide a natural bridge from approximation theory to scientific machine learning.

In Section 7.1, we show that a network with a single hidden layer can approximate any continuous function on a compact set to any desired accuracy. This property is known as the universal approximation property. In Section 7.2, we discuss the role of depth and width. We show by an example that deep networks can represent certain functions with exponentially fewer neurons than shallow networks. Finally, in Section «Click Here», we outline the idea of PINNs and apply it to an ordinary differential equation and to simple linear partial differential equations.

7.1 Universal Approximation by Shallow Networks

Approximating a nonlinear function is challenging because different types of nonlinearities require different function classes for effective approximation. A basic requirement in approximation theory is to identify a function class within which any given function can be approximated to a desired accuracy. Such a property is referred to as universal approximation. In this section, we show that shallow neural networks have this property.

7.1.1 Function Spaces and Universal Approximators

Let \(\mathcal{D}_x\) denote the input or feature space and \(\mathcal{D}_y\) the target or label space. Define a function class

\[ \mathbb{F}(\mathcal{D}_x,\mathcal{D}_y):= \big\{ f:\mathcal{D}_x \rightarrow \mathcal{D}_y~\big|~ f ~ \text{possesses certain properties}\big\}. \]

A hypothesis class is a subclass \(\mathcal{H}\subseteq \mathbb{F}\) from which we seek an approximation to a given target function \(f^*\in \mathbb{F}\).

In what follows, we consider the function class \(\mathbb{F}\) as a linear space equipped with a norm. We call such a normed linear space a function space, especially if it is a Banach space or a Hilbert space.

Example 7.1 (Function Spaces):

Continuous Functions:

Let \(\mathcal{D}_x\subset \mathbb{R}^{n_0}\) be compact and \(\mathcal{D}_y\subseteq \mathbb{R}^{n_L}\). Then,
\[ \mathbb{F}(\mathcal{D}_x,\mathcal{D}_y):= \big\{ f:\mathcal{D}_x \rightarrow \mathcal{D}_y~\big|~ f ~ \text{is continuous}\big\} \]
is a function space with the uniform norm (or supremum norm) defined as
\[ \|f\|_{\infty,\mathcal{D}_x} := \sup\{\|f(\boldsymbol{x})\|~|~\boldsymbol{x}\in \mathcal{D}_x \}, \]
where \(\|\cdot\|\) on the right hand side denotes a vector norm on \(\mathbb{R}^{n_L}\), which is often taken as the Euclidean norm.
We use the notation \(\mathbb{C}(\mathcal{D}_x, \mathcal{D}_y)\) to denote the space of continuous functions. If \(\mathcal{D}_y=\mathbb{R}\), then we write \(\mathbb{C}(\mathcal{D}_x)\).
Since \(\mathcal{D}_x\) is compact, \((\mathbb{C}(\mathcal{D}_x, \mathcal{D}_y), \|\cdot\|_{\infty,\mathcal{D}_x})\) is a Banach space.

Continuously Differentiable Functions:

Let \(\mathcal{D}_x\subset \mathbb{R}^{n_0}\) be compact, \(\mathcal{D}_y\subseteq \mathbb{R}^{n_L}\), and let \(k\in \mathbb{N}\). Then,
\[ \mathbb{F}(\mathcal{D}_x,\mathcal{D}_y):= \big\{ f:\mathcal{D}_x \rightarrow \mathcal{D}_y~\big|~ f ~ \text{is } k\text{-times continuously differentiable}\big\} \]
is a function space with the norm defined as
\[ \|f\|_{\infty,k,\mathcal{D}_x} := \max_{|\boldsymbol{\alpha}|\le k}~\sup\{\|\partial^{\boldsymbol{\alpha}} f(\boldsymbol{x})\|~|~\boldsymbol{x}\in \mathcal{D}_x\}, \]
where \(\boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_{n_0})\in \mathbb{N}_0^{n_0}\) is a multi-index, \(|\boldsymbol{\alpha}|=\alpha_1+\ldots+\alpha_{n_0},\) and \(\mathbb{N}_0^{n_0} = (\mathbb{N}\cup \{0\})^{n_0}\).
We use the notation \(\mathbb{C}^k(\mathcal{D}_x, \mathcal{D}_y)\) to denote the space of \(k\)-times continuously differentiable functions. It is a Banach space since \(\mathcal{D}_x\) is compact. If \(\mathcal{D}_y=\mathbb{R}\), then we write \(\mathbb{C}^k(\mathcal{D}_x)\).

Note:

The space \(\mathbb{C}^k(\mathcal{D}_x)\) is needed in Section «Click Here», where derivatives of a network appear in the cost function.

Solutions of mathematical problems are often functions, and we look for a solution in an appropriate function space. For many problems, a solution is known to exist, but its explicit form is either unknown or too complicated to obtain. In such situations, we look for an approximation to the solution in a hypothesis set. This hypothesis class can approximate every element to any desired accuracy only if it is dense in the function space.

Definition 7.1 (Dense Subset):

A subset \(\mathcal{H}\) of a normed linear space \(\mathbb{F}\) is said to be dense in \(\mathbb{F}\) if for every \(f\in \mathbb{F}\), and every \(\varepsilon>0\), there exists \(h\in \mathcal{H}\) such that

\[ \|f - h\| < \varepsilon. \]

Problem 7.1:

Let \(\mathcal{H}\) be a dense subset of the normed linear space \(\mathbb{F}\). Show that for every \(f\in \mathbb{F}\), there exists a sequence \(\{h_n\}\) in \(\mathcal{H}\) such that \(h_n\rightarrow f\) as \(n\rightarrow \infty\).

We now introduce a notation for families of neural networks.

Remark 7.1 (Family of Feedforward Neural Networks):

Given \(L, \hat{n}, n_0, n_L\in \mathbb{N}\), and an activation function \(\mathscr{A}:\mathbb{R}\rightarrow \mathbb{R}\), the set of all multilayer perceptrons of depth \(L\) and width \(\hat{n}\), with activation \(\mathscr{A}\) in all hidden layers and the identity activation in the output layer, is denoted by

\[ \mathscr{N}_{L,\hat{n}}(\mathscr{A}; n_0, n_L) = \Big\{ {\mathscr{F}_{L,\hat{n}}}: \mathbb{R}^{n_0} \rightarrow \mathbb{R}^{n_L}~\Big|~ \mathscr{A}^{(l)} = \mathscr{A},~ l=1,2,\ldots, L-1,~ \mathscr{A}^{(L)}(x) = x \Big\}. \]

Further, we use the notation

\[ \mathscr{N}_{L}(\mathscr{A}; n_0, n_L) = \displaystyle{\bigcup_{\hat{n}\in \mathbb{N}}} \mathscr{N}_{L,\hat{n}}(\mathscr{A}; n_0, n_L) \]

to denote the set of all multilayer perceptrons of depth \(L\) and arbitrary but finite width.

In particular, every \({\mathscr{F}_{2,\hat{n}}}\in \mathscr{N}_{2,\hat{n}}(\mathscr{A}; 1, 1)\) is a shallow network with one input, one output and \(\hat{n}=n_1\) hidden neurons. With the notations of Chapter 1, it takes the form

\begin{eqnarray} {\mathscr{F}_{2,\hat{n}}}(x) = \sum_{j=1}^{\hat{n}}w^{(2)}_{1j}\, \mathscr{A}\big(w^{(1)}_{j1} x + b^{(1)}_j\big) + b^{(2)}_1,~~ x\in \mathbb{R}, \end{eqnarray}(7.1)

for some \(w^{(1)}_{j1}, b^{(1)}_{j}, w^{(2)}_{1j}, b^{(2)}_{1} \in \mathbb{R}\), \(j=1,2,\ldots, \hat{n}\).

We now define the notion of a universal approximator.

Definition 7.2 (Universal Approximator):

A set \(\mathcal{H}\) of functions defined on \(\mathbb{R}^n\) is called a universal approximator of \(\mathbb{C}(\mathbb{R}^n)\) if, for every compact set \(\mathcal{D}_x \subset \mathbb{R}^n\), the set of restrictions \(\mathcal{H}|_{\mathcal{D}_x} = \{h|_{\mathcal{D}_x} : h \in \mathcal{H}\}\) is dense in \(\mathbb{C}(\mathcal{D}_x)\) with respect to the uniform norm. In other words, for every compact set \(\mathcal{D}_x \subset \mathbb{R}^n\), every \(f \in \mathbb{C}(\mathcal{D}_x)\) and every \(\varepsilon > 0\), there exists \(h \in \mathcal{H}\) such that

\[ \sup_{\boldsymbol{x} \in \mathcal{D}_x} |f(\boldsymbol{x}) - h(\boldsymbol{x})| < \varepsilon. \]

The following is a classical example of a universal approximator.

Example 7.2 (Multivariate Polynomial Functions):

Recall that a polynomial function \(p : \mathbb{R}^n \to \mathbb{R}\) is of the form

\[ p(\boldsymbol{x}) = \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^n} c_{\boldsymbol{\alpha}}\, \boldsymbol{x}^{\boldsymbol{\alpha}},~\boldsymbol{x}=(x_1, x_2, \ldots, x_n)\in \mathbb{R}^n, \]

where only finitely many coefficients \( c_{\boldsymbol{\alpha}} \in \mathbb{R} \) are nonzero. For each multi-index \(\boldsymbol{\alpha}=(\alpha_1, \alpha_2,\ldots, \alpha_n)\in \mathbb{N}_0^n\), the monomial is defined as

\[ \boldsymbol{x}^{\boldsymbol{\alpha}} = \prod_{k=1}^n x_k^{\alpha_k}, \]

and its degree is \( |\boldsymbol{\alpha}| = \alpha_1 + \alpha_2 + \cdots + \alpha_n.\) The degree of the polynomial \( p \) is the largest \( |\boldsymbol{\alpha}| \) such that \( c_{\boldsymbol{\alpha}} \neq 0 \).

By the Stone--Weierstrass theorem, the set of all polynomials is dense in \(\mathbb{C}(\mathcal{D}_x)\) for every compact set \(\mathcal{D}_x\subset \mathbb{R}^n\). Hence, the set of all polynomials on \(\mathbb{R}^n\) is a universal approximator of \(\mathbb{C}(\mathbb{R}^n)\).

7.1.2 Shallow ReLU Networks in One Dimension

In this subsection, we prove that shallow \(\texttt{ReLU}\) networks are universal approximators of \(\mathbb{C}(\mathbb{R})\). The proof has two steps. First, we show that continuous piecewise affine functions are dense in \(\mathbb{C}([a,b])\). Second, we show that every continuous piecewise affine function on \([a,b]\) is a shallow \(\texttt{ReLU}\) network.

Recall, a function \(\varphi:[a,b]\rightarrow \mathbb{R}\) is called a continuous piecewise affine function with respect to a partition \( a = x_0 < x_1 < \cdots < x_N = b \) if \(\varphi\) is continuous on \([a,b]\) and affine on each subinterval \([x_k, x_{k+1}]\), \(k=0,1,\ldots, N-1\).

Lemma 7.1 (Denseness of Continuous Piecewise Affine Functions):

For every \(f \in \mathbb{C}([a,b])\) and every \(\varepsilon > 0\), there exists a continuous piecewise affine function \(\varphi_\varepsilon: [a,b]\rightarrow \mathbb{R}\) such that

\[ \|f - \varphi_\varepsilon\|_{\infty,[a,b]} < \varepsilon. \]

Proof:

Let \(f \in \mathbb{C}([a,b])\) and \(\varepsilon>0\) be given.

Since \(f\) is continuous on the compact interval \([a,b]\), it is uniformly continuous. Hence, there exists \(\delta=\delta(\varepsilon)>0\) such that \(|f(x)-f(y)|<\varepsilon\) whenever \(x,y\in[a,b]\) and \(|x-y|<\delta\). Choose \(N\in \mathbb{N}\) sufficiently large so that \((b-a)/N<\delta\). Then, on the uniform partition

\[ a = x_0 < x_1 < \dots < x_N = b,~~x_k = a + k\frac{b-a}{N}, \]

we have

\[ |f(x) - f(y)| < \varepsilon, \quad \text{for all } x,y \in [x_k, x_{k+1}],~k=0,\dots,N-1. \]

Define the piecewise affine function

\[ \varphi_\varepsilon(x) = f(x_k) + t\big(f(x_{k+1}) - f(x_{k})\big),~ \text{for}~ x=x_k+t (x_{k+1}-x_k),~\text{with}~t\in [0,1], \]

for \(k=0,1,\ldots, N-1\). The function \(\varphi_\varepsilon\) is continuous on \([a,b]\) and interpolates \(f\) at the nodes \(x_k\).

Let \(x\in [a,b]\) be arbitrary. Choose \(k\in \{0,1,\ldots, N-1\}\) such that \(x\in [x_k, x_{k+1}]\). The value \(\varphi_\varepsilon(x)\) lies between \(f(x_k)\) and \(f(x_{k+1})\). Since \(f\) is continuous, by the intermediate value theorem, there exists \(\xi\in [x_k, x_{k+1}]\) such that

\[ \varphi_\varepsilon(x) = f(\xi). \]

Since \(x,\xi\in [x_k, x_{k+1}]\), by the choice of the partition, we have

\[ |f(x) - \varphi_\varepsilon(x)|= |f(x) - f(\xi)| < \varepsilon. \]

Since this estimate holds for every \(x\in [a,b]\), and the supremum of the continuous function \(|f-\varphi_\varepsilon|\) over the compact set \([a,b]\) is attained, we have

\[ \|f-\varphi_\varepsilon\|_{\infty, [a,b]} = \max_{x\in [a,b]} |f(x) - \varphi_\varepsilon(x)| < \varepsilon. \]

Remark 7.2 (Number of Neurons for Lipschitz Functions):

The above proof does not give a bound on \(N\) for a general continuous function. However, suppose that \(f\) is Lipschitz continuous on \([a,b]\) with Lipschitz constant \(\Lambda>0\). Then

\[ |f(x) - \varphi_\varepsilon(x)| = |f(x) - f(\xi)| \le \Lambda\,|x-\xi| \le \Lambda\,\frac{b-a}{N}. \]

Hence, the choice

\[ N > \frac{\Lambda (b-a)}{\varepsilon} \]

is sufficient. We will see in Lemma 7.2 that \(N\) is the number of hidden neurons of the corresponding shallow \(\texttt{ReLU}\) network.

We now show that every continuous piecewise affine function on \([a,b]\) is exactly a shallow \(\texttt{ReLU}\) network.

Lemma 7.2 (Continuous Piecewise Affine Functions as Shallow ReLU Networks):

Let \(\varphi:[a,b]\rightarrow \mathbb{R}\) be a continuous piecewise affine function with respect to the partition \(a = x_0 < x_1 < \cdots < x_N = b\). Then, there exists \({\mathscr{F}_{2,N}}\in \mathscr{N}_{2,N}(\mathscr{R}_0; 1, 1)\) such that

\[ {\mathscr{F}_{2,N}}(x) = \varphi(x),~~\text{for all}~x\in [a,b], \]

where \(\mathscr{R}_0\) is the \(\texttt{ReLU}\) function defined in (1.6).

Proof:

Choose \(w^{(1)}_{j1} = 1,\) \(b^{(1)}_j = -x_{j-1},\) for \(j=1,2,\ldots, N,\) \(\hat{n} = N\), and \(\mathscr{A} = \mathscr{R}_0\). From (7.1), we get

\[ {\mathscr{F}_{2,N}}(x) = \sum_{j=1}^{N}w^{(2)}_{1j}\, \mathscr{R}_0\big(x - x_{j-1}\big) + b^{(2)}_1,~~ x\in [a,b]. \]

Imposing the condition \({\mathscr{F}_{2,N}}(x_0) = \varphi(x_0)\), we get

\[b^{(2)}_1 = \varphi(x_0).\]

Let

\[ m_k = \frac{\varphi(x_{k+1}) - \varphi(x_k)}{x_{k+1}-x_k},~~k=0,1,\ldots, N-1, \]

denote the slope of \(\varphi\) on \([x_k, x_{k+1}]\).

For \(x\in [x_0, x_1]\), the condition \({\mathscr{F}_{2,N}}(x) = \varphi(x)\) reads

\[ {\mathscr{F}_{2,N}}(x) = \varphi(x_0) + m_0 (x-x_0). \]

Comparing with the general expression of \({\mathscr{F}_{2,N}}(x)\), we get \(w^{(2)}_{11} = m_0\).

For any \(k=1,2,\ldots, N-1\), let \(x\in [x_k, x_{k+1}]\). Then we have

\begin{eqnarray} {\mathscr{F}_{2,N}}(x) &=& \sum_{j=1}^{k+1}w^{(2)}_{1j}\, \mathscr{R}_0\big(x - x_{j-1}\big) + b^{(2)}_1\\ &=& \sum_{j=1}^{k+1}w^{(2)}_{1j}\, \big(x - x_{j-1}\big) + \varphi(x_0) . \end{eqnarray}(7.2)

Thus, \({\mathscr{F}_{2,N}}\) is affine on \([x_k, x_{k+1}]\). Let us take

\begin{eqnarray} w^{(2)}_{1j} = m_{j-1} - m_{j-2},~~j=2,3,\ldots, N. \end{eqnarray}(7.3)

Then, its slope on the interval \([x_k, x_{k+1}]\) is

\[ \sum_{j=1}^{k+1}w^{(2)}_{1j} = m_0 + \sum_{j=2}^{k+1}\big(m_{j-1} - m_{j-2}\big) = m_k. \]

Hence, on each subinterval \([x_k,x_{k+1}]\), the functions \({\mathscr{F}_{2,N}}\) and \(\varphi\) are affine with the same slope \(m_k\).

It remains to show that \({\mathscr{F}_{2,N}}(x_k) = \varphi(x_k),~~ k=0,1,2,\ldots, N\). We prove this by induction on \(k\).

For \(k=0\), we have \({\mathscr{F}_{2,N}}(x_0) = \varphi(x_0)\). Assume that \({\mathscr{F}_{2,N}}(x_k) = \varphi(x_k)\). Since \({\mathscr{F}_{2,N}}\) and \(\varphi\) are affine with the same slope in \([x_k, x_{k+1}]\), we have \({\mathscr{F}_{2,N}}(x_{k+1}) = \varphi(x_{k+1})\).

Two affine functions that takes the same value at \(x_k\) and \(x_{k+1}\) coincide on \([x_k,x_{k+1}]\). Hence, \({\mathscr{F}_{2,N}}(x) = \varphi(x)\) for all \(x\in [a,b]\).

We now state and prove the main result of this subsection.

Theorem 7.1 (Universal Approximation by Shallow ReLU Networks):

The class \(\mathscr{N}_{2}(\mathscr{R}_0; 1, 1)\) is a universal approximator of \(\mathbb{C}(\mathbb{R})\).

Proof:

Let \(\mathcal{D}_x\subset\mathbb{R}\) be compact, and let \(f\in\mathbb{C}(\mathcal{D}_x)\) and \(\varepsilon>0\) be given. We have to show that there exists \({\mathscr{F}_{2,\hat{n}_\varepsilon}}\in\mathscr{N}_{2}(\mathscr{R}_0;1,1)\) such that

\[ \|f-{\mathscr{F}_{2,\hat{n}_\varepsilon}}\|_{\infty,\mathcal{D}_x}<\varepsilon. \]

Since \(\mathcal{D}_x\) is compact, it is closed and bounded in \(\mathbb{R}\). Hence, there is a closed and bounded interval \([a,b]\) with \(\mathcal{D}_x\subset[a,b]\). By the Tietze extension theorem, there exists a continuous function \(\widetilde f\) on \([a,b]\) such that \(\widetilde f|_{\mathcal{D}_x} = f\).

By Lemma 7.1, there exists a continuous piecewise affine function \(\varphi_\varepsilon\) on a partition of \([a,b]\) with \(\hat{n}_\varepsilon\) subintervals such that

\[ \|\widetilde{f}-\varphi_\varepsilon\|_{\infty,[a,b]}<\varepsilon. \]

By Lemma 7.2, there exists \({\mathscr{F}_{2,\hat{n}_\varepsilon}}\in\mathscr{N}_{2}(\mathscr{R}_0;1,1)\) such that \({\mathscr{F}_{2,\hat{n}_\varepsilon}}(x) = \varphi_\varepsilon(x)\) for all \(x\in[a,b]\). Restricting to \(\mathcal{D}_x\subset[a,b]\) yields

\begin{eqnarray} \|f-{\mathscr{F}_{2,\hat{n}_\varepsilon}}\|_{\infty,\mathcal{D}_x} &=& \sup_{x\in\mathcal{D}_x} |\widetilde f(x)-\varphi_\varepsilon(x)|\\ &\le& \sup_{x\in[a,b]} |\widetilde f(x)-\varphi_\varepsilon(x)| \\ &=& \|\widetilde{f}-\varphi_\varepsilon\|_{\infty,[a,b]}< \varepsilon. \end{eqnarray}(7.4)

Since \(\mathcal{D}_x\) and \(f\) were arbitrary, \(\mathscr{N}_2(\mathscr{R}_0;1,1)\) is a universal approximator of \(\mathbb{C}(\mathbb{R})\).

The following problem shows that shallow networks with the Heaviside activation also approximate continuous functions uniformly on an interval, although the network functions themselves are discontinuous.

Problem 7.2 (Shallow Heaviside Networks):

Let \(f \in \mathbb{C}([a,b])\) and \(\varepsilon > 0\).

Show that there exists a step function \(s_\varepsilon:[a,b]\rightarrow \mathbb{R}\), constant on each \([x_k,x_{k+1})\) of a uniform partition, such that \(\|f - s_\varepsilon\|_{\infty,[a,b]} < \varepsilon\).
Show that there exists \({\mathscr{F}_{2,\hat{n}_\varepsilon}} \in \mathscr{N}_{2}(\mathscr{H}; 1, 1)\), for some \(\hat{n}_\varepsilon\in \mathbb{N}\), such that \(\|f - {\mathscr{F}_{2,\hat{n}_\varepsilon}}\|_{\infty,[a,b]} < \varepsilon\).

7.1.3 General Activation Functions

The universal approximation property is not restricted to the \(\texttt{ReLU}\) activation or to one dimension. In this subsection, we state two classical results without proof. The first result is for sigmoidal activation functions.

Definition 7.3 (Sigmoidal Function):

A function \(\varphi:\mathbb{R}\to\mathbb{R}\) is said to be sigmoidal if

\[ \lim_{t\to -\infty}\varphi(t) = 0, \qquad \lim_{t\to +\infty}\varphi(t) = 1. \]

Note:

The logistic functions \(\mathscr{S}_k\), \(k>0\), defined in (1.5) are sigmoidal functions. A sigmoidal function in the above sense need not be monotone or differentiable.

Theorem 7.2 (Cybenko Theorem):

Let \(\mathscr{S}:\mathbb{R}\rightarrow \mathbb{R}\) be a continuous sigmoidal function and let \(I_{n_0}=[0,1]^{n_0}\). Then, the restrictions of the networks in \(\mathscr{N}_{2}(\mathscr{S}; n_0, 1)\) to \(I_{n_0}\) form a dense subset of \(\mathbb{C}(I_{n_0})\).

The proof uses the Hahn--Banach theorem and the Riesz representation theorem. We omit it in this course.

The next theorem characterizes the continuous activation functions for which shallow networks are universal approximators.

Theorem 7.3 (Leshno--Lin--Pinkus--Schocken Theorem):

Let \(\mathscr{A}:\mathbb{R}\rightarrow \mathbb{R}\) be continuous. Then, the class of shallow networks \(\mathscr{N}_{2}(\mathscr{A}; n_0, 1)\) is a universal approximator of \(\mathbb{C}(\mathbb{R}^{n_0})\) if and only if \(\mathscr{A}\) is not a polynomial.

The proof of the above theorem is omitted for this course.

Note:

The activation functions \(\mathscr{S}_k\), \(\tanh\), \(\mathscr{R}_\alpha\) (\(0\le \alpha<1\)), \(\texttt{SLU}_k\) and the softplus function are continuous and are not polynomials. Hence, shallow networks with any of these activations are universal approximators. On the other hand, if \(\mathscr{A}\) is the identity function, then every network in \(\mathscr{N}_{2}(\mathscr{A}; n_0, 1)\) is an affine function. The class of affine functions is not dense in \(\mathbb{C}(\mathcal{D}_x)\).

Remark 7.3 (Universality is an Existence Result):

The universal approximation theorems guarantee that an approximating network exists. They do not give a bound on the number of neurons for a general continuous function. Remark 7.2 gives such a bound in one dimension for Lipschitz functions. The theorems also say nothing about whether a training algorithm finds the approximating network.

7.2 Role of Depth and Width

The results of the previous section show that depth is not necessary for universal approximation. A single hidden layer is sufficient if the width is allowed to be arbitrarily large. Nevertheless, deep networks are preferred in practice. In this section, we show by an example that depth can reduce the number of neurons needed to represent a function. We also state a result showing that depth can compensate for a bounded width.

7.2.1 Depth: The Sawtooth Example

Consider the hat function \(g:[0,1]\rightarrow [0,1]\) defined by

\begin{eqnarray} g(x) = \left\{\begin{array}{ll} 2x, & \text{if}~0\le x\le \tfrac{1}{2},\\ 2-2x, & \text{if}~\tfrac{1}{2}< x\le 1. \end{array}\right. \end{eqnarray}(7.5)

Since \(g\) maps \([0,1]\) into \([0,1]\), we can define \(g_k:[0,1]\rightarrow[0,1]\), for \(k\in \mathbb{N}\), recursively by

\[ g_1 = g, \qquad g_{k+1} = g\circ g_k,~~k\in\mathbb{N}. \]

Thus, \(g_k\) is the \(k\)-fold composition of \(g\) with itself.

Problem 7.3:

Show that

\[ g(x) = 2\,\mathscr{R}_0(x) - 4\,\mathscr{R}_0\big(x-\tfrac{1}{2}\big),~~\text{for all}~x\in [0,1]. \]

From the above representation of \(g\), can you observe that \(g\) can be written as a neural network on the interval \([0,1]\)? If so, what are the width and depth of this network? Provide the activation function of each layer and give the number of weights and biases.

The graph of \(g_{k}\) is a sawtooth. The next proposition counts its linear pieces.

Lemma 7.3 (Pieces of the Sawtooth Function):

For every \(k\in\mathbb{N}\), the function \(g_{k}\) is continuous piecewise affine on \([0,1]\) with respect to the uniform partition

\[ x_{j,k} = \frac{j}{2^k},~~j=0,1,\ldots, 2^k. \]

The function \(g_{k}\) is an affine bijection from \(I_{j,k}=[x_{j,k}, x_{j+1,k}]\) onto \([0,1]\), with slope \((-1)^j 2^k\) on \((x_{j,k}, x_{j+1,k})\).

Proof:

We use induction on \(k\). For \(k=1\), the statement follows from (7.5). The pieces are \(I_{0,1}=[0,\tfrac{1}{2}]\) and \(I_{1,1}=[\tfrac{1}{2},1]\), with slopes \(2\) and \(-2\).

Assume that the statement holds for some \(k\in \mathbb{N}\), and write \(g_{k+1} = g\circ g_{k}\). Fix \(j\in\{0,1,\ldots,2^k-1\}\). The two halves of \(I_{j,k}\) are

\[ I_{2j,k+1}=[x_{2j,k+1},x_{2j+1,k+1}] \quad\text{and}\quad I_{2j+1,k+1}=[x_{2j+1,k+1},x_{2j+2,k+1}], \]

and their common endpoint \(x_{2j+1,k+1}\) is the midpoint of \(I_{j,k}\).

By the induction hypothesis, \(g_{k}\) is an affine bijection from \(I_{j,k}\) onto \([0,1]\) with slope \((-1)^j 2^k\). Hence, it maps the midpoint of \(I_{j,k}\) to \(\tfrac{1}{2}\), and it maps each half of \(I_{j,k}\) bijectively onto one of the intervals \([0,\tfrac{1}{2}]\) and \([\tfrac{1}{2},1]\).

Case 1: \(j\) even. Then \(g_{k}\) is increasing on \(I_{j,k}\). It maps \(I_{2j,k+1}\) onto \([0,\tfrac{1}{2}]\), where \(g\) has slope \(2\), and it maps \(I_{2j+1,k+1}\) onto \([\tfrac{1}{2},1]\), where \(g\) has slope \(-2\).

Case 2: \(j\) odd. Then \(g_{k}\) is decreasing on \(I_{j,k}\). It maps \(I_{2j,k+1}\) onto \([\tfrac{1}{2},1]\), where \(g\) has slope \(-2\), and it maps \(I_{2j+1,k+1}\) onto \([0,\tfrac{1}{2}]\), where \(g\) has slope \(2\).

In both cases, \(g_{k+1}\) is a composition of two affine bijections on each half of \(I_{j,k}\). Hence, it is an affine bijection from each half onto \([0,1]\). Its slope is the product of the two slopes. In both cases, this gives

\[ 2^{k+1}~~\text{on}~I_{2j,k+1}, \qquad -2^{k+1}~~\text{on}~I_{2j+1,k+1}. \]

Since \((-1)^{2j}=1\) and \((-1)^{2j+1}=-1\), the slope of \(g_{k+1}\) on \(I_{i,k+1}\) is \((-1)^i 2^{k+1}\) for every \(i=0,1,\ldots,2^{k+1}-1\). This proves the statement for \(k+1\).

Finally, consecutive slopes have opposite signs. Hence, each of the \(2^k-1\) interior nodes is a breakpoint, and \(g_{k}\) has exactly \(2^k\) affine pieces.

In the next proposition, we show that \(g_{k}\) is represented by a deep \(\texttt{ReLU}\) network.

Lemma 7.4 (Deep Network for the Sawtooth Function):

For every \(k\in\mathbb{N}\), there exists \({\mathscr{F}_{k+1,2}}\in \mathscr{N}_{k+1,2}(\mathscr{R}_0; 1, 1)\) such that

\[ {\mathscr{F}_{k+1,2}}(x) = g_{k}(x),~~\text{for all}~x\in[0,1]. \]

Proof:

By Problem 7.3, we have

\[ g(x) = {\mathscr{F}_{2,2}}(x;\boldsymbol{\Theta}_1),~~x\in[0,1], \]

where

\[ \boldsymbol{\Theta}_1 = \left(\overline{W}^{(1)}, \overline{W}^{(2)}\right) = \left( \left(\begin{array}{cc}0&1\\-\frac{1}{2}&1\end{array}\right),~ \left(\begin{array}{ccc}0&2&-4\end{array}\right) \right), \]

with \(\underset{\overline{~~~~}}{\mathscr{A}}^{(1)} = \mathscr{R}_0\) (componentwise) and \(\mathscr{A}^{(2)} = \text{id}\). This proves the proposition for \(k=1\).

For illustration, consider \(k=2\). Since \(g(x)\in[0,1]\) for \(x\in[0,1]\), we can apply the above representation to \(g(x)\) and get

\begin{eqnarray} g_2(x) &=& g(g(x))\\ &=& {\mathscr{F}_{2,2}}(g(x);\boldsymbol{\Theta}_1)\\ &=& {\mathscr{F}_{2,2}}({\mathscr{F}_{2,2}}(x;\boldsymbol{\Theta}_1) ;\boldsymbol{\Theta}_1)\\ &=&{\mathscr{F}_{2,2}}\Big(2\,\mathscr{R}_0(x) - 4\,\mathscr{R}_0\big(x-\tfrac{1}{2}\big);\boldsymbol{\Theta}_1\Big)\\ &=&2\,\mathscr{R}_0\Big(2\,\mathscr{R}_0(x) - 4\,\mathscr{R}_0\big(x-\tfrac{1}{2}\big)\Big) - 4\,\mathscr{R}_0\big(2\,\mathscr{R}_0(x) - 4\,\mathscr{R}_0\big(x-\tfrac{1}{2}\big)-\tfrac{1}{2}\big) \end{eqnarray}(7.6)

Take

\[ \boldsymbol{x}^{(1)} = \left(\begin{array}{c}\mathscr{R}_0(x)\\\mathscr{R}_0\big(x-\tfrac{1}{2}\big)\end{array}\right),~~ \boldsymbol{x}^{(2)} = \left(\begin{array}{c}\mathscr{R}_0\big(2x^{(1)}_1 - 4x^{(1)}_2\big)\\\mathscr{R}_0\big(2x^{(1)}_1 - 4x^{(1)}_2-\tfrac{1}{2}\big)\end{array}\right),~~ x^{(3)} = 2x^{(2)}_1 - 4 x^{(2)}_2. \]

Then \(g_2(x) = x^{(3)}\). This is the forward propagation of \(x\) through two hidden layers, each having two neurons with ReLU activation, and an output layer with identity activation. Therefore,

\[ g_2(x) = {\mathscr{F}_{3,2}}(x;\boldsymbol{\Theta}_2),~~x\in[0,1], \]

where

\[ \boldsymbol{\Theta}_2 = \left(\overline{W}^{(1)}, \overline{W}^{(2)}, \overline{W}^{(3)}\right) = \left( \left(\begin{array}{cc}0&1\\-\frac{1}{2}&1\end{array}\right),~ \left(\begin{array}{ccc}0&2&-4\\-\frac{1}{2}&2&-4\end{array}\right),~ \left(\begin{array}{ccc}0&2&-4\end{array}\right) \right). \]

We now prove the proposition for general \(k\) by induction. For \(k\in\mathbb{N}\), define

\[ \boldsymbol{\Theta}_k = \left(\overline{W}^{(1)}, \overline{W}^{(2)}, \ldots, \overline{W}^{(k)}, \overline{W}^{(k+1)}\right), \]

where

\[ \overline{W}^{(1)} = \left(\begin{array}{cc}0&1\\-\frac{1}{2}&1\end{array}\right),~~ \overline{W}^{(l)}=\left(\begin{array}{ccc}0&2&-4\\-\frac{1}{2}&2&-4\end{array}\right),~l=2,\ldots, k,~~ \overline{W}^{(k+1)}=\left(\begin{array}{ccc}0&2&-4\end{array}\right), \]

with the activation \(\mathscr{R}_0\) in the hidden layers and the identity activation in the output layer. We show that

\[ g_k(x) = {\mathscr{F}_{k+1,2}}(x;\boldsymbol{\Theta}_k),~~x\in[0,1]. \]

The case \(k=1\) is proved above. Assume that the statement holds for some \(k\in\mathbb{N}\). Let \(x\in[0,1]\), and let \(\boldsymbol{x}^{(k)}=(x^{(k)}_1,x^{(k)}_2)^\top\) be the activation of the last hidden layer of \({\mathscr{F}_{k+1,2}}(\,\cdot\,;\boldsymbol{\Theta}_k)\) at \(x\). By the induction hypothesis and the form of the output layer,

\[ g_k(x) = 2x^{(k)}_1 - 4x^{(k)}_2. \]

Since \(g_k(x)\in[0,1]\), Problem 7.3 gives

\begin{eqnarray} g_{k+1}(x) &=& g\big(g_k(x)\big)\\ &=& 2\,\mathscr{R}_0\big(g_k(x)\big) - 4\,\mathscr{R}_0\big(g_k(x)-\tfrac{1}{2}\big)\\ &=& 2\,\mathscr{R}_0\big(2x^{(k)}_1 - 4x^{(k)}_2\big) - 4\,\mathscr{R}_0\big(2x^{(k)}_1 - 4x^{(k)}_2-\tfrac{1}{2}\big). \end{eqnarray}(7.7)

The two terms

\[ x^{(k+1)}_1 = \mathscr{R}_0\big(2x^{(k)}_1 - 4x^{(k)}_2\big),~~ x^{(k+1)}_2 = \mathscr{R}_0\big(2x^{(k)}_1 - 4x^{(k)}_2-\tfrac{1}{2}\big) \]

form the activation of a new hidden layer with augmented weight matrix

\[ \overline{W}^{(k+1)}=\left(\begin{array}{ccc}0&2&-4\\-\frac{1}{2}&2&-4\end{array}\right) \]

and activation \(\mathscr{R}_0\). Moreover, \(g_{k+1}(x) = 2x^{(k+1)}_1 - 4x^{(k+1)}_2\), which is the output layer with augmented weight matrix \(\left(\begin{array}{ccc}0&2&-4\end{array}\right)\) and identity activation.

Therefore, a neural network representation of \(g_{k+1}\) is obtained by inserting a hidden layer in the neural network representation of \(g_k\) before the output layer with the augmented weight as given above with activation \(\mathscr{R}_0\) and thus can be written as

\[ g_{k+1}(x) = {\mathscr{F}_{k+2,2}}(x;\boldsymbol{\Theta}_{k+1}),~~x\in[0,1]. \]

This completes the induction and the proof.

We now show that a shallow \(\texttt{ReLU}\) network needs exponentially many neurons to represent \(g_{k}\).

Theorem 7.4 (Pieces of a Shallow ReLU Network):

Every \({\mathscr{F}_{2,\hat{n}}}\in \mathscr{N}_{2,\hat{n}}(\mathscr{R}_0; 1, 1)\) is a continuous piecewise affine function on \(\mathbb{R}\) with at most \(\hat{n}\) breakpoints and its restriction to any interval has at most \(\hat{n}+1\) affine pieces.

Proof:

For \(j=1,2,\ldots,\hat{n}\), write the \(j\)-th term in (7.1) as

\[ \phi_j(x) = \mathscr{R}_0\big(w^{(1)}_{j1} x + b^{(1)}_j\big),~~x\in\mathbb{R}. \]

Then, we can write

\[ {\mathscr{F}_{2,\hat{n}}}(x) = \sum_{j=1}^{\hat{n}}w^{(2)}_{1j}\, \phi_j(x) + b^{(2)}_1. \]

Step 1: Each \(\phi_j\) is continuous and has at most one breakpoint. The function \(\phi_j\) is continuous, since it is the composition of the continuous function \(\mathscr{R}_0\) with an affine function. We consider two cases.

If \(w^{(1)}_{j1}=0\), then \(\phi_j(x)=\mathscr{R}_0\big(b^{(1)}_j\big)\) is constant on \(\mathbb{R}\).
If \(w^{(1)}_{j1}\neq 0\), define \(\xi_j = -b^{(1)}_j/w^{(1)}_{j1}\). Then \(w^{(1)}_{j1} x + b^{(1)}_j = w^{(1)}_{j1}(x-\xi_j)\). This expression has one sign on \((-\infty,\xi_j]\) and the opposite sign on \([\xi_j,\infty)\). On the side where it is non-negative, \(\phi_j(x) = w^{(1)}_{j1}(x-\xi_j)\). On the other side, \(\phi_j(x)=0\). Hence, \(\phi_j\) is affine on \((-\infty,\xi_j]\) and on \([\xi_j,\infty)\).

Step 2: The network is continuous and has at most \(\hat{n}\) breakpoints. Let \(P\) be the set of points \(\xi_j\) for those \(j\) with \(w^{(1)}_{j1}\neq 0\). Then \(P\) has \(m\le \hat{n}\) elements. Order them as \(p_1 < p_2 < \cdots < p_m\). These points divide \(\mathbb{R}\) into the \(m+1\) intervals

\[ (-\infty,p_1],~[p_1,p_2],~\ldots,~[p_{m-1},p_m],~[p_m,\infty). \]

None of these intervals contains a point of \(P\) in its interior. Hence, by Step 1, every \(\phi_j\) is affine on each of these intervals. Since

\[ {\mathscr{F}_{2,\hat{n}}}(x) = \sum_{j=1}^{\hat{n}} w^{(2)}_{1j}\,\phi_j(x) + b^{(2)}_1, \]

the network \({\mathscr{F}_{2,\hat{n}}}\) is also affine on each of these intervals. It is continuous on \(\mathbb{R}\), since it is a linear combination of continuous functions plus a constant. Therefore, \({\mathscr{F}_{2,\hat{n}}}\) is continuous and piecewise affine on \(\mathbb{R}\). Its breakpoints lie in \(P\), so it has at most \(\hat{n}\) breakpoints.

Step 3: Restriction to an interval. Let \(I\subseteq\mathbb{R}\) be an interval. The function \({\mathscr{F}_{2,\hat{n}}}\) is affine on the intersection of \(I\) with each of the \(m+1\) intervals of Step 2. Hence, its restriction to \(I\) has at most \(m+1\le \hat{n}+1\) affine pieces.

Corollary 7.1 (Shallow Networks for the Sawtooth Function):

Let \(k\in\mathbb{N}\). There exists \({\mathscr{F}_{2,2^k}}\in \mathscr{N}_{2,2^k}(\mathscr{R}_0; 1, 1)\) such that

\[ {\mathscr{F}_{2,2^k}}(x) = g_{k}(x),~~\text{for all}~x\in[0,1]. \]

Moreover, if \({\mathscr{F}_{2,\hat{n}}}\in \mathscr{N}_{2,\hat{n}}(\mathscr{R}_0; 1, 1)\) satisfies \({\mathscr{F}_{2,\hat{n}}}(x) = g_{k}(x)\) for all \(x\in[0,1]\), then \(\hat{n}\ge 2^k\).

Proof:

Step 1: [Existence]
By the above Lemma 7.3, \(g_k\) is continuous piecewise affine on \([0,1]\) with respect to the partition \(x_{j,k}=j/2^k\), \(j=0,1,\ldots,2^k\). This partition has \(2^k\) subintervals. Hence, by Lemma 7.2, there exists \({\mathscr{F}_{2,2^k}}\) such that \({\mathscr{F}_{2,2^k}}=g_k\) on \([0,1]\).

Step 2: [Lower bound] Let \({\mathscr{F}_{2,\hat{n}}}=g_k\) on \([0,1]\). By Lemma 7.3, the slope of \(g_k\) changes at each of the \(2^k-1\) points \(x_{j,k}\), \(j=1,2,\ldots,2^k-1\). Each such point is a breakpoint of \({\mathscr{F}_{2,\hat{n}}}\). By Theorem 7.4, \({\mathscr{F}_{2,\hat{n}}}\) has at most \(\hat{n}\) breakpoints. Hence, \(\hat{n}\ge 2^k-1\).

Suppose that \(\hat{n}=2^k-1\). Then every neuron has a breakpoint, and these breakpoints are exactly the points \(x_{j,k}\), \(j=1,2,\ldots,2^k-1\). After relabelling the neurons, the \(j\)-th neuron has \(w^{(1)}_{j1}\neq 0\) and breakpoint \(x_{j,k}\). Let \(s_j\) be the sign of \(w^{(1)}_{j1}\). Since \(\mathscr{R}_0\) is positively homogeneous,

\[ \mathscr{R}_0\big(w^{(1)}_{j1}x+b^{(1)}_j\big) = |w^{(1)}_{j1}|\,\mathscr{R}_0\big(s_j(x-x_{j,k})\big). \]

Hence, on \([0,1]\),

\[ {\mathscr{F}_{2,\hat{n}}}(x) = b^{(2)}_1 + \sum_{j=1}^{2^k-1} a_j\,\mathscr{R}_0\big(s_j(x-x_{j,k})\big),~~a_j = w^{(2)}_{1j}\,|w^{(1)}_{j1}|. \]

If \(s_j=1\), the \(j\)-th term has slope \(0\) to the left of \(x_{j,k}\) and slope \(a_j\) to the right. If \(s_j=-1\), it has slope \(-a_j\) to the left and slope \(0\) to the right. In both cases, its slope jumps by \(a_j\) at \(x_{j,k}\). The other terms are affine near \(x_{j,k}\). By Lemma 7.3, the slope of \(g_k\) jumps at \(x_{j,k}\) by

\[ (-1)^j2^k-(-1)^{j-1}2^k = (-1)^j\,2^{k+1}. \]

Hence, \(a_j=(-1)^j2^{k+1}\) for every \(j\).

Let \(J=\{j : s_j=-1\}\). On \((0,x_{1,k})\), the terms with \(s_j=1\) vanish, and the terms with \(j\in J\) have slope \(-a_j\). The slope of \(g_k\) on this interval is \(2^k\). Hence,

\[ -\sum_{j\in J} (-1)^j\,2^{k+1} = 2^k,~~\text{that is,}~~\sum_{j\in J}(-1)^j = -\frac{1}{2}. \]

The left-hand side is an integer. This is a contradiction. Hence, \(\hat{n}\ge 2^k\).

Remark 7.4 (Depth and Efficiency):

The deep network of Lemma 7.4 represents \(g_{k}\) with \(2k\) hidden neurons. By Corollary 7.1, a shallow network needs \(2^k\) hidden neurons. For example, for \(k=10\), the deep network has \(20\) hidden neurons, whereas a shallow network needs \(1024\).

The above comparison concerns exact representation. Telgarsky (2016) proves a stronger result for approximation. Networks with fewer layers need exponentially many neurons even to approximate \(g_{k}\) to a fixed accuracy in the \(L^1\) norm.

Thus, depth does not increase the class of functions that can be approximated. It can reduce the number of neurons needed to approximate a given function.

Problem 7.4:

Consider a network \({\mathscr{F}_{L,\hat{n}}}\in \mathscr{N}_{L,\hat{n}}(\mathscr{R}_0; 1, 1)\), with \(L\ge 2\), in which every hidden layer has \(\hat{n}\) neurons.

Show that the number of hidden neurons is \(N=(L-1)\hat{n}\), and that the number of trainable parameters (weights and biases) is
\[ P = 3\hat{n}+1 + (L-2)\,\hat{n}(\hat{n}+1). \]
Deduce that
\[ P = (\hat{n}+1)\,N - \hat{n}^2 + 2\hat{n} + 1. \]
Hence, for a fixed width \(\hat{n}\), the number of parameters is an affine function of the number of neurons.
Find the number of trainable parameters of the network of Lemma 7.4.
Using Corollary 7.1, find a lower bound on the number of trainable parameters of a shallow network that represents \(g_k\) on \([0,1]\).
Compare the two numbers for \(k=10\).

7.2.2 Width: Deep Networks of Bounded Width

In Section 7.1, we have discussed the universal approximation results by fixing the depth at two and letting the width grow. One may also fix the width and let the depth grow. The following result, which we state without proof, answers the question of how narrow a deep \(\texttt{ReLU}\) network can be.

Theorem 7.5 (Hanin--Sellke Theorem):

Let \(n_0\in\mathbb{N}\). The class

\[ \bigcup_{L\in\mathbb{N}} \mathscr{N}_{L,n_0+1}(\mathscr{R}_0; n_0, 1) \]

of \(\texttt{ReLU}\) networks of width \(n_0+1\) and arbitrary depth is a universal approximator of \(\mathbb{C}(\mathbb{R}^{n_0})\). Moreover, \(\texttt{ReLU}\) networks of width \(n_0\) and arbitrary depth are not universal approximators of \(\mathbb{C}(\mathbb{R}^{n_0})\).

Remark 7.5 (Width versus Depth):

Shallow networks achieve universality through width (Section 7.1). Narrow networks achieve universality through depth (Theorem 7.5). In practice, both depth and width are chosen together, and the choice is guided by experiments.