In 2012, a deep learning architecture revolutionized the field of computer vision by achieving unprecedented performance in the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) [4]. The deep learning architecture, known as AlexNet, significantly outperformed all competing approaches. A few years later, in March 2016, a deep learning-based architecture called AlphaGo defeated the best Go player at the time, Lee Sedol, in a five-game match [5]. Go is a highly complex board game with a vast number of possible moves, making it a challenging problem for artificial intelligence. Because of this complexity, many researchers believed that defeating a top human Go player was a feat that would only be achieved decades later.

These breakthroughs along with many others, including DeepMind’s AlphaFold [6], which revolutionized protein structure prediction in 2020, the unprecedented language capabilities of large language models like GPT-3 (and later versions) [7, 8], and the emergence of generative AI models like Stable Diffusion, Midjourney, and DALL-E, have sparked interest among scientists across (almost) all disciplines. Likewise, while mathematical research on neural networks has a long history, these groundbreaking developments revived interest in the theoretical underpinnings of deep learning among mathematicians. However, initially, there was a clear consensus in the mathematics community: We do not understand why this technology works so well! In fact, there are many mathematical reasons that, at least superficially, should prevent the observed success.

Over the past decade the field has matured, and mathematicians have gained a more profound understanding of deep learning, although many open questions remain. Recent years have brought various new explanations and insights into the inner workings of these models. Before discussing them in detail in the following chapters, we first give a high-level introduction to deep learning, with a focus on the supervised learning framework for function approximation, which is the central theme of this book.

Deep learning refers to the application of deep neural networks trained by gradient-based methods, to identify unknown input-output relationships. This approach has three key ingredients: deep neural networks, gradient-based training, and prediction. We now explain each of these ingredients separately.

2.2.1 Deep Neural Networks

Deep neural networks are formed by a combination of neurons. A neuron is a function of the form

\[ \begin{align} \mathbb{R}^d \ni {\boldsymbol{x}} \mapsto \nu({\boldsymbol{x}}) = \sigma( {\boldsymbol{w}}^\top {\boldsymbol{x}} +b ), \end{align} \]

(1)

where \( {\boldsymbol{w}} \in \mathbb{R}^d\) is a weight vector, \( b\in \mathbb{R}\) is called bias, and the function \( \sigma\) is referred to as an activation function. This concept is due to McCulloch and Pitts [9] and is a mathematical model for biological neurons. If we consider \( \sigma\) to be the Heaviside function, i.e., \( \sigma = \boldsymbol{1}_{\mathbb{R}_+}\) with \( \mathbb{R}_+\mathrm{:}= [0,\infty)\) , then the neuron “fires” if the weighted sum of the inputs \( {\boldsymbol{x}}\) surpasses the threshold \( -b\) . We depict a neuron in Figure 1. Note that if we fix \( d\) and \( \sigma\) , then the set of neurons can be naturally parameterized by the \( d+1\) real values \( w_1,\dots,w_d,b\in\mathbb{R}\) .

Neural networks are functions formed by connecting neurons, where the output of one neuron becomes the input to another. One simple but very common type of neural network is the so-called feedforward neural network. This structure distinguishes itself by having the neurons grouped in layers, and the inputs to neurons in the \( (\ell+1)\) -st layer are exclusively neurons from the \( \ell\) -th layer.

We start by defining a shallow feedforward neural network as an affine transformation applied to the output of a set of neurons that share the same input and the same activation function. Here, an affine transformation is a map \( T:\mathbb{R}^p\to\mathbb{R}^q\) such that \( T({\boldsymbol{x}})={\boldsymbol{W}}{\boldsymbol{x}}+{\boldsymbol{b}}\) for some \( {\boldsymbol{W}}\in\mathbb{R}^{q\times p}\) , \( {\boldsymbol{b}}\in\mathbb{R}^q\) where \( p\) , \( q \in \mathbb{N}\) .

Formally, a shallow feedforward neural network is, therefore, a map \( \Phi\) of the form

\[ \mathbb{R}^d \ni {\boldsymbol{x}} \mapsto \Phi({\boldsymbol{x}}) = T_1\circ\sigma\circ T_0({\boldsymbol{x}}) \]

where \( T_0\) , \( T_1\) are affine transformations and the application of \( \sigma\) is understood to be in each component of \( T_1({\boldsymbol{x}})\) . A visualization of a shallow neural network is given in Figure 2.

A deep feedforward neural network is constructed by compositions of shallow neural networks. This yields a map of the type

\[ \mathbb{R}^d \ni {\boldsymbol{x}} \mapsto \Phi({\boldsymbol{x}}) = T_{L+1}\circ\sigma\circ \cdots \circ T_1 \circ\sigma\circ T_0({\boldsymbol{x}}), \]

where \( L \in \mathbb{N}\) and \( (T_j)_{j= 0}^{L+1}\) are affine transformations. The number of compositions \( L\) is referred to as the number of layers of the deep neural network. Similar to a single neuron, (deep) neural networks can be viewed as a parameterized function class, with the parameters being the entries of the matrices and vectors determining the affine transformations \( (T_j)_{j= 0}^{L+1}\) .

2.2.2 Gradient-based training

2.2.3 Prediction

The final part of deep learning concerns the question of whether we have actually learned something by the procedure above. Suppose that our optimization routine has either converged or has been terminated, yielding a neural network \( \Phi_*\) . While the optimization aimed to minimize the empirical risk on the training sample \( S\) , our ultimate interest is not in how well \( \Phi_*\) performs on \( S\) . Rather, we are interested in its performance on new data points \( ({\boldsymbol{x}}_{\rm {new}}, {\boldsymbol{y}}_{\rm new})\) outside of \( S\) .

To make meaningful statements about this, we assume existence of a data distribution \( \mathcal{D}\) on the input-output space—in our case, this is \( \mathbb{R}^d \times \mathbb{R}^k\) —such that both the elements of \( S\) and all other data points are drawn from this distribution. In other words, we treat \( S\) as an i.i.ddraw from \( \mathcal{D}\) , and \( ({\boldsymbol{x}}_{\rm {new}}, {\boldsymbol{y}}_{\rm new})\) also as sampled independently from \( \mathcal{D}\) . If we want \( \Phi_*\) to perform well on average, then this amounts to controlling the following expression

\[ \begin{align} \mathcal{R}(\Phi_*) = \mathbb{E}_{({\boldsymbol{x}}_{\rm new}, {\boldsymbol{y}}_{\rm new}) \sim \mathcal{D}}[\mathcal{L}(\Phi_*({\boldsymbol{x}}_{\rm new}), {\boldsymbol{y}}_{\rm new})], \end{align} \]

(4)

which is called the risk of \( \Phi_*\) . If the risk is not much larger than the empirical risk, then we say that the neural network \( \Phi_*\) has a small generalization error. On the other hand, if the risk is much larger than the empirical risk, then we say that \( \Phi_*\) overfits the training data, meaning that \( \Phi_*\) has memorized the training samples, but does not generalize well to data outside of the training set.

It is natural to wonder why the deep learning pipeline, as outlined in the previous subsection, ultimately succeeds in learning, i.e., achieving a small risk. Is it true that for a given sample \( ({\boldsymbol{x}}_i,{\boldsymbol{y}}_i)_{i=1}^m\) there exist a neural network such that \( \Phi({\boldsymbol{x}}_i) \approx {\boldsymbol{y}}_i\) for all \( i = 1, \dots m\) ? Does the optimization routine produce a meaningful result? Can we control the risk, knowing only that the empirical risk is small?

While most of these questions can be answered affirmatively under certain assumptions, these assumptions often do not apply to deep learning in practice. We next explore some potential explanations and show that they lead to even more questions.

2.3.1 Approximation

2.3.2 Optimization

2.3.3 Generalization

This book addresses the questions raised in the previous section, providing answers that are mathematically rigorous and accessible. Our focus will be on provable statements, presented in a manner that prioritizes simplicity and clarity over generality. We will sometimes illustrate key ideas only in special cases, or under strong assumptions, both to avoid an overly technical exposition, and because definitive answers are often not yet available. In the following, we summarize the content of each chapter and highlight parts pertaining to the questions stated in the previous section.

Chapter 3: Feedforward neural networks. In this chapter, we introduce the main object of study of this book—the feedforward neural network.

Chapter 4: Universal approximation. We present the classical view of function approximation by neural networks, and give two instances of so-called universal approximation results. Such statements describe the ability of neural networks to approximate every function of a given class to arbitrary accuracy, given that the network size is sufficiently large. The first result, which holds under very broad assumptions on the activation function, is on uniform approximation of continuous functions on compact domains. The second result shows that for a very specific activation function, the network size can be chosen independently of the desired accuracy, highlighting that universal approximation needs to be interpreted with caution.

Chapter 5: Splines. Going beyond universal approximation, this chapter starts to explore approximation rates of neural networks. Specifically, we examine how well certain functions can be approximated relative to the number of parameters in the network. For so-called sigmoidal activation functions, we establish a link between neural-network- and spline-approximation. This reveals that smoother functions require fewer network parameters. However, achieving this increased efficiency necessitates the use of deeper neural networks. This observation offers a first glimpse into the importance of depth in deep learning.

Chapter 6: ReLU neural networks. This chapter focuses on one of the most popular activation functions in practice—the ReLU. We prove that the class of ReLU networks is equal to the set of continuous piecewise linear functions, thus providing a theoretical foundation for their expressive power. Furthermore, given a continuous piecewise linear function, we investigate the necessary width and depth of a ReLU network to represent it. Finally, we leverage approximation theory for piecewise linear functions to derive convergence rates for approximating Hölder continuous functions.

Chapter 7: Affine pieces for ReLU neural networks. Having gained some intuition about ReLU neural networks, in this chapter, we adress some potential limitations. We analyze ReLU neural networks by counting the number of affine regions that they generate. The key insight of this chapter is that deep neural networks can generate exponentially more regions than shallow ones. This observation provides further evidence for the potential advantages of depth in neural network architectures.

Chapter 8: Deep ReLU neural networks. Having identified the ability of deep ReLU neural networks to generate a large number of affine regions, we investigate whether this translates into an actual advantage in function approximation. Indeed, for approximating smooth functions, we prove substantially better approximation rates than we obtained for shallow neural networks. This adds again to our understanding of depth and its connections to expressive power of neural network architectures.

Chapter 9: High-dimensional approximation. The convergence rates established in the previous chapters deteriorate significantly in high-dimensional settings. This chapter examines three scenarios under which neural networks can provably overcome the curse of dimensionality.

Chapter 10: Interpolation. In this chapter we shift our perspective from approximation to exact interpolation of the training data. We analyze conditions under which exact interpolation is possible, and discuss the implications for empirical risk minimization. Furthermore, we present a constructive proof showing that ReLU networks can express an optimal interpolant of the data (in a specific sense).

Chapter 11: Training of neural networks. We start to examine the training process of deep learning. First, we study the fundamentals of (stochastic) gradient descent and convex optimization. Additionally, we examine accelerated methods and highlight the key principles behind popular training algorithms such as Adam. Finally, we discuss how the backpropagation algorithm can be used to implement these optimization algorithms for training neural networks.

Chapter 12: Wide neural networks and the neural tangent kernel. This chapter introduces the neural tangent kernel as a tool for analyzing the training behavior of neural networks. We begin by revisiting linear and kernel regression for the approximation of functions based on data. Additionally we discuss the effect of adding a regularization term to the objective function. Afterwards, we show for certain architectures of sufficient width, that the training dynamics of gradient descent resemble those of kernel regression and converge to a global minimum. This analysis provides insights into why, under certain conditions, we can train neural networks without getting stuck in (bad) local minima, despite the non-convexity of the objective function. Finally, we discuss a well-known link between neural networks and Gaussian processes, giving some indication why overparameterized networks do not necessarily overfit in practice.

Chapter 13: Loss landscape analysis. In this chapter, we present an alternative view on the optimization problem, by analyzing the loss landscape—the empirical risk as a function of the neural network parameters. We give theoretical arguments showing that increasing overparameterization leads to greater connectivity between the valleys and basins of the loss landscape. Consequently, overparameterized architectures make it easier to reach a region where all minima are global minima. Additionally, we observe that most stationary points associated with non-global minima are saddle points. This sheds further light on the empirically observed fact that deep architectures can often be optimized without getting stuck in non-global minima.

Chapter 14: Shape of neural network spaces. While Chapters 12 and 13 highlight potential reasons for the success of neural network training, in this chapter, we show that the set of neural networks of a fixed architecture has some undesirable properties from an optimization perspective. Specifically, we show that this set is typically non-convex. Moreover, in general it does not possess the best-approximation property, meaning that there might not exist a neural network within the set yielding the best approximation for a given function.

Chapter 15 : Generalization properties of deep neural networks. To understand why deep neural networks successfully generalize to unseen data points (outside of the training set), we study classical statistical learning theory, with a focus on neural network functions as the hypothesis class. We then show how to establish generalization bounds for deep learning, providing theoretical insights into the performance on unseen data.

Chapter 16: Generalization in the overparameterized regime. The generalization bounds of the previous chapter are not meaningful when the number of parameters of a neural network surpasses the number of training samples. However, this overparameterized regime is where many successful network architectures operate. To gain a deeper understanding of generalization in this regime, we describe the phenomenon of double descent and present a potential explanation. This addresses the question of why deep neural networks perform well despite being highly overparameterized.

Chapter 17: Robustness and adversarial examples. In the final chapter, we explore the existence of adversarial examples—inputs designed to deceive neural networks. We provide some theoretical explanations of why adversarial examples arise, and discuss potential strategies to prevent them.

This book studies some central topics of deep learning but leaves out even more. Interesting questions associated with the field that were omitted, as well as some pointers to related works are listed below:

Advanced architectures: The (deep) feedforward neural network is far from the only type of neural network. In practice, architectures must be adapted to the type of data. For example, images exhibit strong spatial dependencies in the sense that adjacent pixels often have similar values. Convolutional neural networks [10] are particularly well suited for this type of input, as they employ convolutional filters that aggregate information from neighboring pixels, thus capturing the data structure better than a fully connected feedforward network. Similarly, graph neural networks [11] are a natural choice for graph-based data. For sequential data, such as natural language, architectures with some form of memory component are used, including Long Short-Term Memory (LSTM) networks [12] and attention-based architectures like transformers [7].

Unsupervised and Reinforcement Learning: While this book focuses on supervised learning, where each data point \( x_i\) has a label \( y_i\) , there is a vast field of machine learning called unsupervised learning, where labels are absent. Classical unsupervised learning problems include clustering and dimensionality reduction [13, Chapters 22/23].

A popular area in deep learning, where no labels are used, is physics-informed neural networks [14]. Here, a neural network is trained to satisfy a partial differential equation (PDE), with the loss function quantifying the deviation from this PDE.

Finally, reinforcement learning is a technique where an agent can interact with an environment and receives feedback based on its actions. The actions are guided by a so-called policy, which is to be learned, [15, Chapter 17]. In deep reinforcement learning, this policy is modeled by a deep neural network. Reinforcement learning is the basis of the aforementioned AlphaGo.

Interpretability/Explainability and Fairness: The use of deep neural networks in critical decision-making processes, such as allocating scarce resources (e.g., organ transplants in medicine, financial credit approval, hiring decisions) or engineering (e.g., optimizing bridge structures, autonomous vehicle navigation, predictive maintenance), necessitates an understanding of their decision-making process. This is crucial for both practical and ethical reasons.

Practically, understanding how a model arrives at a decision can help us improve its performance and mitigate problems. It allows us to ensure that the model performs according to our intentions and does not produce undesirable outcomes. For example, in bridge design, understanding why a model suggests or rejects a particular configuration can help engineers identify potential vulnerabilities, ultimately leading to safer and more efficient designs. Ethically, transparent decision-making is crucial, especially when the outcomes have significant consequences for individuals or society; biases present in the data or model design can lead to discriminatory outcomes, making explainability essential.

However, explaining the predictions of deep neural networks is not straightforward. Despite knowledge of the network weights and biases, the repeated and complex interplay of linear transformations and non-linear activation functions often renders these models black boxes. A comprehensive overview of various techniques for interpretability, not only for deep neural networks, can be found in [16]. Regarding the topic of fairness, we refer for instance to [17, 18].

Implementation: While this book focuses on provable theoretical results, the field of deep learning is strongly driven by applications, and a thorough understanding of deep learning cannot be achieved without practical experience. For this, there exist numerous resources with excellent explanations. We recommend [19, 20, 21] as well as the countless online tutorials that are just a Google (or alternative) search away.

Many more: The field is evolving rapidly, and new ideas are constantly being generated and tested. This book cannot give a complete overview. However, we hope that it provides the reader with a solid foundation in the fundamental knowledge and principles to quickly grasp and understand new developments in the field.

Throughout this book, we will end each chapter with a short overview of related work and the references used in the chapter.

In this introductory chapter, we highlight several other recent textbooks and works on deep learning. For a historical survey on neural networks see [22] and also [23]. For general textbooks on neural networks and deep learning, we refer to [24, 25, 21] for more recent monographs. More mathematical introductions to the topic are given, for example, in [26, 3, 27]. For the implementation of neural networks we refer for example to [19, 20].

We previously defined a single neuron \( \nu\) in (1) and Figure 1. A neural network is constructed by connecting multiple neurons. Let us now make precise this connection procedure.

The architecture of a neural network is often depicted as a connected graph, as illustrated in Figure 4. The nodes in such graphs represent (the output of) the neurons. They are arranged in layers, with \( {\boldsymbol{x}}^{(\ell)}\) in Definition 1 corresponding to the neurons in layer \( \ell\) . We also refer to \( {\boldsymbol{x}}^{(0)}\) in (5.a) as the input layer and to \( {\boldsymbol{x}}^{(L+1)}\) in (5.c) as the output layer. All layers in between are referred to as the hidden layers and their output is given by (5.b). The number of hidden layers corresponds to the depth. For the correct interpretation of such graphs, we note that by our conventions in Definition 1, the activation function is applied after each affine transformation, except in the final layer.

Neural networks of depth one are called shallow, if the depth is larger than one they are called deep. The notion of deep neural networks is not used entirely consistently in the literature, and some authors use the word deep only in case the depth is much larger than one, where the precise meaning of “much larger” depends on the application.

Throughout, we only consider neural networks in the sense of Definition 1. We emphasize however, that this is just one (simple but very common) type of neural network. Many adjustments to this construction are possible and also widely used. For example:

• We may use different activation functions \( \sigma_\ell\) in each layer \( \ell\) or we may even use a different activation function for each node.
• Residual neural networks allow “skip connections” [28]. This means that information is allowed to skip layers in the sense that the nodes in layer \( \ell\) may have \( {\boldsymbol{x}}^{(0)},\dots,{\boldsymbol{x}}^{(\ell-1)}\) as their input (and not just \( {\boldsymbol{x}}^{(\ell-1)}\) ), cf. (5).
• In contrast to feedforward neural networks, recurrent neural networks allow information to flow backward, in the sense that \( {\boldsymbol{x}}^{(\ell-1)},\dots,{\boldsymbol{x}}^{(L+1)}\) may serve as input for the nodes in layer \( \ell\) (and not just \( {\boldsymbol{x}}^{(\ell-1)}\) ). This creates loops in the flow of information, and one has to introduce a time index \( t\in\mathbb{N}\) , as the output of a node in time step \( t\) might be different from the output in time step \( t+1\) .

Let us clarify some further common terminology used in the context of neural networks:

• parameters: The parameters of a neural network refer to the set of all entries of the weight matrices and bias vectors. These are often collected in a single vector

  \[ \begin{equation} {\boldsymbol{w}}=(({\boldsymbol{W}}^{(0)},{\boldsymbol{b}}^{(0)}),\dots,({\boldsymbol{W}}^{(L)},{\boldsymbol{b}}^{(L)})). \end{equation} \]

  (6)

  These parameters are adjustable and are learned during the training process, determining the specific function realized by the network.
• hyperparameters: Hyperparameters are settings that define the network’s architecture (and training process), but are not directly learned during training. Examples include the depth, the number of neurons in each layer, and the choice of activation function. They are typically set before training begins.
• weights: The term “weights” is often used broadly to refer to all parameters of a neural network, including both the weight matrices and bias vectors.
• model: For a fixed architecture, every choice of network parameters \( {\boldsymbol{w}}\) as in (6) defines a specific function \( {\boldsymbol{x}}\mapsto \Phi_{\boldsymbol{w}}({\boldsymbol{x}})\) . In deep learning this function is often referred to as a model. More generally, “model” can be used to describe any function parameterization by a set of parameters \( {\boldsymbol{w}}\in\mathbb{R}^n\) , \( n \in \mathbb{N}\) .

3.1.1 Basic operations on neural networks

Neural networks provide a framework to parametrize functions. Ultimately, our goal is to find a neural network that fits some underlying input-output relation. As mentioned above, the architecture (depth, width and activation function) is typically chosen apriori and considered fixed. During training of the neural network, its parameters (weights and biases) are suitably adapted by some algorithm. Depending on the application, on top of the stated architecture choices, further restrictions on the weights and biases can be desirable. For example, the following two appear frequently:

• weight sharing: This is a technique where specific entries of the weight matrices (or bias vectors) are constrained to be equal. Formally, this means imposing conditions of the form \( W_{k,l}^{(i)}=W^{(j)}_{s,t}\) , i.e the entry \( (k,l)\) of the \( i\) th weight matrix is equal to the entry at position \( (s,t)\) of weight matrix \( j\) . We denote this assumption by \( (i,k,l)\sim (j,s,t)\) , paying tribute to the trivial fact that “\( \sim\) ” is an equivalence relation. During training, shared weights are updated jointly, meaning that any change to one weight is simultaneously applied to all other weights of this class. Weight sharing can also be applied to the entries of bias vectors.
• sparsity: This refers to imposing a sparsity structure on the weight matrices (or bias vectors). Specifically, we apriorily set \( W_{k,l}^{(i)}=0\) for certain \( (k,l,i)\) , i.ewe impose entry \( (k,l)\) of the \( i\) th weight matrix to be \( 0\) . These zero-valued entries are considered fixed, and are not adjusted during training. The condition \( W_{k,l}^{(i)}=0\) corresponds to node \( l\) of layer \( i-1\) not serving as an input to node \( k\) in layer \( i\) . If we represent the neural network as a graph, this is indicated by not connecting the corresponding nodes. Sparsity can also be imposed on the bias vectors.

Both of these restrictions decrease the number of learnable parameters in the neural network. The number of parameters can be seen as a measure of the complexity of the represented function class. For this reason, we introduce \( \rm{ size}(\Phi)\) as a notion for the number of learnable parameters. Formally (with \( |S|\) denoting the cardinality of a set \( S\) ):

Activation functions are a crucial part of neural networks, as they introduce nonlinearity into the model. If an affine activation function were used, the resulting neural network function would also be affine and hence very restricted in what it can represent.

The choice of activation function can have a significant impact on the performance, but there does not seem to be a universally optimal one. We next discuss a few important activation functions and highlight some common issues associated with them.

Sigmoid: The sigmoid activation function is given by

and depicted in Figure 5 (a). Its output ranges between zero and one, making it interpretable as a probability. The sigmoid is a smooth function, which allows the application of gradient-based training.

It has the disadvantage that its derivative becomes very small if \( |x| \to \infty\) . This can affect learning due to the so-called vanishing gradient problem. Consider the simple neural network \( \Phi_n(x) = \sigma \circ \dots \circ \sigma(x + b)\) defined with \( n \in \mathbb{N}\) compositions of \( \sigma\) , and where \( b\in\mathbb{R}\) is a bias. Its derivative with respect to \( b\) is

If \( \sup_{x\in\mathbb{R}}|\sigma'(x)|\le 1-\delta\) , then by induction, \( |\frac{\,\mathrm{d}}{\,\mathrm{d} b} \Phi_n(x)|\le (1-\delta)^n\) . The opposite effect happens for activation functions with derivatives uniformly larger than one. This argument shows that the derivative of \( \Phi_n(x,b)\) with respect to \( b\) can become exponentially small or exponentially large when propagated through the layers. This effect, known as the vanishing- or exploding gradient effect, also occurs for activation functions which do not admit the uniform bounds assumed above. However, since the sigmoid activation function exhibits areas with extremely small gradients, the vanishing gradient effect can be strongly exacerbated.

ReLU (Rectified Linear Unit): The ReLU is defined as

and depicted in Figure 5 (b). It is piecewise linear, and due to its simplicity its evaluation is computationally very efficient. It is one of the most popular activation functions in practice. Since its derivative is always zero or one, it does not suffer from the vanishing gradient problem to the same extent as the sigmoid function. However, ReLU can suffer from the so-called dead neurons problem. Consider the neural network

depending on the bias \( b\in\mathbb{R}\) . If \( b < 0\) , then \( \Phi(x) = 0\) for all \( x \in \mathbb{R}\) . The neuron corresponding to the second application of \( \sigma_{\rm {ReLU}}\) thus produces a constant signal. Moreover, if \( b < 0\) , \( \frac{\,\mathrm{d}}{\,\mathrm{d} b}\Phi(x)=0\) for all \( x\in\mathbb{R}\) . As a result, every negative value of \( b\) yields a stationary point of the empirical risk. A gradient-based method will not be able to further train the parameter \( b\) . We thus refer to this neuron as a dead neuron.

SiLU (Sigmoid Linear Unit): An important difference between the ReLU and the Sigmoid is that the ReLU is not differentiable at \( 0\) . The SiLU activation function (also referred to as “swish”) can be interpreted as a smooth approximation to the ReLU. It is defined as

and is depicted in Figure 5 (b). There exist various other smooth activation functions that mimic the ReLU, including the Softplus \( x\mapsto \log(1+\exp(x))\) , the GELU (Gaussian Error Linear Unit) \( x\mapsto xF(x)\) where \( F(x)\) denotes the cumulative distribution function of the standard normal distribution, and the Mish \( x\mapsto x\tanh(\log(1+\exp(x)))\) .

Parametric ReLU or Leaky ReLU: This variant of the ReLU addresses the dead neuron problem. For some \( a\in (0,1)\) , the parametric ReLU is defined as

and is depicted in Figure 5 (c) for three different values of \( a\) . Since the output of \( \sigma\) does not have flat regions like the ReLU, the dying ReLU problem is mitigated. If \( a\) is not chosen too small, then there is less of a vanishing gradient problem than for the Sigmoid. In practice, the additional parameter \( a\) has to be fine-tuned depending on the application. Like the ReLU, the parametric ReLU is not differentiable at \( 0\) .

The concept of neural networks was first introduced by McCulloch and Pitts in [9]. Later Rosenblatt [29] introduced the perceptron, an artificial neuron with adjustable weights that forms the basis of the multilayer perceptron (a fully connected feedforward neural network). The vanishing gradient problem shortly addressed in Section 3.3 was discussed by Hochreiter in his diploma thesis [30] and later in [31, 12].

To analyze what kind of functions can be approximated with neural networks, we start by considering the uniform approximation of continuous functions \( f:\mathbb{R}^d\to\mathbb{R}\) on compact sets. To this end, we first introduce the notion of compact convergence.

Throughout what follows, we always consider \( C^0(\mathbb{R}^d)\) equipped with the topology of Definition 3 (also see Exercise 5), and every subset such as \( C^0(D)\) with the subspace topology: for example, if \( D\subseteq\mathbb{R}^d\) is bounded, then convergence in \( C^0(D)\) refers to uniform convergence \( \lim_{n\to\infty}\sup_{x\in D}|f_n(x)-f(x)|=0\) .

4.1.1 Universal approximators

4.1.2 Shallow neural networks

4.1.3 Deep neural networks

4.1.4 Other norms

In the previous section, we saw that a large class of activation functions allow for universal approximation. However, these results did not provide any insights into the necessary neural network size for achieving a specific accuracy.

Before exploring this topic further in the following chapters, we next present a remarkable result that shows how the required neural network size is significantly influenced by the choice of activation function. The result asserts that, with the appropriate activation function, every \( f\in C^0(K)\) on a compact set \( K\subseteq\mathbb{R}^d\) can be approximated to every desired accuracy \( \varepsilon>0\) using a neural network of size \( O(d^2)\) ; in particular the neural network size is independent of \( \varepsilon>0\) , \( K\) , and \( f\) . We will first discuss the one-dimensional case.

To extend this result to arbitrary dimension, we will use Kolmogorov’s superposition theorem. It states that every continuous function of \( d\) variables can be expressed as a composition of functions that each depend only on one variable. We omit the technical proof, which can be found in [36].

Kolmogorov’s superposition theorem is intriguing as it shows that approximating \( d\) -dimensional functions can be reduced to the (generally much simpler) one-dimensional case through compositions. Neural networks, by nature, are well suited to approximate functions with compositional structures. However, the functions \( f_j\) in Theorem 3, even though only one-dimensional, could become very complex and challenging to approximate themselves if \( d\) is large.

Similarly, the “magic” activation function in Proposition 4 encodes the information of all rational polynomials on the unit interval, which is why a neural network of size \( O(1)\) suffices to approximate every function to arbitrary accuracy. Naturally, no practical algorithm can efficiently identify appropriate neural network weights and biases for this architecture. As such, the results presented in Section 4.2 should be taken with a pinch of salt as their practical relevance is highly limited. Nevertheless, they highlight that while universal approximation is a fundamental and important property of neural networks, it leaves many aspects unexplored. To gain further insight into practically relevant architectures, in the following chapters, we investigate neural networks with activation functions such as the ReLU.

The foundation of universal approximation theorems goes back to the late 1980s with seminal works by Cybenko [37], Hornik et al[38, 39], Funahashi [40] and Carroll and Dickinson [41]. These results were subsequently extended to a wider range of activation functions and architectures. The present analysis in Section 4.1 closely follows the arguments in [32], where it was essentially shown that universal approximation can be achieved if the activation function is not polynomial. The proof of Lemma 1 is from [34, Theorem 2.1], with earlier results of this type being due to [42].

Kolmogorov’s superposition theorem stated in Theorem 3 was originally proven in 1957 [36]. For a more recent and constructive proof see for instance [43]. Kolmogorov’s theorem and its obvious connections to neural networks have inspired various research in this field, e.g [44, 45, 46, 47, 48], with its practical relevance being debated [49, 50]. The idea for the “magic” activation function in Section 4.2 comes from [51] where it is shown that such an activation function can even be chosen monotonically increasing.

We introduce a simple type of spline and its approximation properties below.

By shifting and dilating the cardinal B-spline, we obtain a system of univariate splines. Taking tensor products of these univariate splines yields a set of higher-dimensional functions known as the multivariate B-splines.

Having introduced the system \( \mathcal{B}^n\) , we would like to understand how well we can represent each smooth function by superpositions of elements of \( \mathcal{B}^n\) . The following theorem is adapted from the more general result [1, Theorem 7]; also see [2, Theorem D.3] for a presentation closer to the present formulation.

We now show that the approximation rates of B-splines can be transfered to certain neural networks. The following argument is based on [1].

Our goal in the following is to show that neural networks can approximate a linear combination of \( N\) B-splines with a number of parameters that is proportional to \( N\) . As an immediate consequence of Theorem 4, we then obtain a convergence rate for neural networks. Let us start by approximating a single univariate B-spline with a neural network of fixed size.

Next, we extend Proposition 5 to the multivariate splines \( \mathcal{S}_{\ell, {\boldsymbol{t}}, n}^d\) for arbitrary \( \ell\) , \( d \in \mathbb{N}\) , \( {\boldsymbol{t}} \in \mathbb{R}^d\) .

Proposition 6 shows that we can approximate a single multivariate B-spline with a neural network with a size that is independent of the accuracy. Combining this observation with Theorem 4 leads to the following result.

Theorem 5 shows that neural networks with higher-order sigmoidal functions can approximate smooth functions with the same accuracy as spline approximations while having a comparable number of parameters. The network depth is required to behave like \( O(\log(k))\) in terms of the smoothness parameter \( k\) , cp. Remark 3.

The argument of linking sigmoidal activation functions with spline based approximation was first introduced in [52, 55]. For further details on spline approximation, see [53] or the book [56].

The general strategy of approximating basis functions by neural networks, and then lifting approximation results for those bases has been employed widely in the literature, and will also reappear again in this book. While the following chapters primarily focus on ReLU activation, we highlight a few notable approaches with non-ReLU activations based on the outlined strategy: To approximate analytic functions, [57] emulates a monomial basis. To approximate periodic functions, a basis of trigonometric polynomials is recreated in [58]. Wavelet bases have been emulated in [59]. Moreover, neural networks have been studied through the representation system of ridgelets [60] and ridge functions [61]. A general framework describing the emulation of representation systems to transfer approximation results was presented in [62].

The goal of this section is to formalize how to combine and manipulate ReLU neural networks. We have seen an instance of such a result already in Proposition 1. Now we want to make this result more precise under the assumption that the activation function is the ReLU. We sharpen Proposition 1 by adding bounds on the number of weights that the resulting neural networks have. The following four operations form the basis of all constructions in the sequel.

• Reproducing an identity: We have seen in Proposition 3 that for most activation functions, an approximation to the identity can be built by neural networks. For ReLUs, we can have an even stronger result and reproduce the identity exactly. This identity will play a crucial role in order to extend certain neural networks to deeper neural networks, and to facilitate an efficient composition operation.
• Composition: We saw in Proposition 1 that we can produce a composition of two neural networks and the resulting function is a neural network as well. There we did not study the size of the resulting neural networks. For ReLU activation functions, this composition can be done in a very efficient way leading to a neural network that has up to a constant not more than the number of weights of the two initial neural networks.
• Parallelization: Also the parallelization of two neural networks was discussed in Proposition 1. We will refine this notion and make precise the size of the resulting neural networks.
• Linear combinations: Similarly, for the sum of two neural networks, we will give precise bounds on the size of the resulting neural network.

6.1.1 Identity

6.1.2 Composition

6.1.3 Parallelization

6.1.4 Linear combinations

In this section, we will relate ReLU neural networks to a large class of functions. We first formally introduce the set of continuous piecewise linear functions from a set \( \Omega\subseteq\mathbb{R}^d\) to \( \mathbb{R}\) . Note that we admit in particular \( \Omega=\mathbb{R}^d\) in the following definition.

In the following, we will refer to the connected domains on which \( f\) is equal to one of the functions \( g_j\) , also as regions or pieces. If \( f\) is cpwl with \( q\in\mathbb{N}\) regions, then with \( n \in \mathbb{N}\) denoting the number of affine functions it holds \( n\le q\) .

Note that, the mapping \( {\boldsymbol{x}} \mapsto \sigma_{\rm {ReLU}}({\boldsymbol{w}}^\top{\boldsymbol{x}}+b)\) , which is a ReLU neural network with a single neuron, is cpwl (with two regions). Consequently, every ReLU neural network is a repeated composition of linear combinations of cpwl functions. It is not hard to see that the set of cpwl functions is closed under compositions and linear combinations. Hence, every ReLU neural network is a cpwl function. Interestingly, the reverse direction of this statement is also true, meaning that every cpwl function can be represented by a ReLU neural network as we shall demonstrate below. Therefore, we can identify the class of functions realized by arbitrary ReLU neural networks as the class of cpwl functions.

A statement similar to Theorem 6 can be found in [2, 3]. There, the authors give a construction with a depth that behaves logarithmic in \( d\) and is independent of \( n\) , but with significantly larger bounds on the size. As we shall see, the proof of Theorem 6 is a simple consequence of the following well-known result from [4]; also see [5], and for sharper bounds [6]. It states that every cpwl function can be expressed as a finite maximum of a finite minimum of certain affine functions.

To prove Theorem 6, it therefore suffices to show that the minimum and the maximum are expressible by ReLU neural networks.

The minimum of \( n\ge 2\) inputs can be computed by repeatedly applying the construction of Lemma 10. The resulting neural network is described in the next lemma.

This section studies the case, where we do not have arbitrary cpwl functions, but where the regions on which \( f\) is affine are simplices. Under this condition, we can construct neural networks that scale merely linearly in the number of such regions, which is a serious improvement from the exponential dependence of the size on the number of regions that was found in Theorem 6.

6.3.1 Triangulations of \( \Omega\)

For the ensuing discussion, we will consider \( \Omega\subseteq\mathbb{R}^d\) to be partitioned into simplices. This partitioning will be termed a triangulation of \( \Omega\) . Other notions prevalent in the literature include a tessellation of \( \Omega\) , or a simplicial mesh on \( \Omega\) . To give a precise definition, let us first recall some terminology. For a set \( S\subseteq\mathbb{R}^d\) we denote the convex hull of \( S\) by

\[ \begin{align} {\rm co}(S)\mathrm{:}= \left\{\sum_{j=1}^n\alpha_j {\boldsymbol{x}}_j\, \middle|\,n\in\mathbb{N},~{\boldsymbol{x}}_j\in S,\alpha_j\ge 0,~\sum_{j=1}^n\alpha_j=1\right\}. \end{align} \]

(40)

An \( n\) -simplex is the convex hull of \( n\in \mathbb{N}\) points that are independent in a specific sense. This is made precise in the following definition.

Definition 11

Let \( n\in\mathbb{N}_0\) , \( d\in\mathbb{N}\) and \( n\le d\) . We call \( {\boldsymbol{x}}_0,\dots,{\boldsymbol{x}}_n\in\mathbb{R}^d\) affinely independent if and only if either \( n=0\) or \( n\ge 1\) and the vectors \( {\boldsymbol{x}}_1-{\boldsymbol{x}}_0,\dots,{\boldsymbol{x}}_n-{\boldsymbol{x}}_0\) are linearly independent. In this case, we call \( {\rm {co}}({\boldsymbol{x}}_0,\dots,{\boldsymbol{x}}_n)\mathrm{:}={\rm co}(\{{\boldsymbol{x}}_0,\dots,{\boldsymbol{x}}_n\})\) an \( n\) -simplex.

As mentioned before, a triangulation refers to a partition of a space into simplices. We give a formal definition below.

Definition 12

Let \( d\in\mathbb{N}\) , and \( \Omega\subseteq\mathbb{R}^d\) be compact. Let \( \mathcal{T}\) be a finite set of \( d\) -simplices, and for each \( \tau\in\mathcal{T}\) let \( V(\tau)\subseteq \Omega\) have cardinality \( d+1\) such that \( \tau={\rm {co}}(V(\tau))\) . We call \( \mathcal{T}\) a regular triangulation of \( \Omega\) , if and only if

1. \( \bigcup_{\tau\in\mathcal{T}}\tau = \Omega\) ,
2. for all \( \tau\) , \( \tau'\in\mathcal{T}\) it holds that \( \tau\cap\tau'={\rm {co}}(V(\tau)\cap V(\tau'))\) .

We call \( {\boldsymbol{\eta}}\in \mathcal{V}\mathrm{:}= \bigcup_{\tau\in\mathcal{T}}V(\tau)\) a node (or vertex) and \( \tau\in\mathcal{T}\) an element of the triangulation.

For a regular triangulation \( \mathcal{T}\) with nodes \( \mathcal{V}\) we also introduce the constant

\[ \begin{align} k_\mathcal{T}\mathrm{:}= \max_{{\boldsymbol{\eta}}\in\mathcal{V}}|\{\tau\in\mathcal{T}\,|\,{\boldsymbol{\eta}}\in\tau\}| \end{align} \]

(41)

corresponding to the maximal number of elements shared by a single node.

6.3.2 Size bounds for regular triangulations

Throughout this subsection, let \( \mathcal{T}\) be a regular triangulation of \( \Omega\) , and we adhere to the notation of Definition 12. We will say that \( f:\Omega\to\mathbb{R}\) is cpwl with respect to \( \mathcal{T}\) if \( f\) is cpwl and \( f|_\tau\) is affine for each \( \tau\in\mathcal{T}\) . The rest of this subsection is dedicated to proving the following result. It was first shown in [7] with a more technical argument, and extends an earlier statement from [3] to general triangulations (also see Section 6.3.3).

Theorem 7

Let \( d \in \mathbb{N}\) , \( \Omega\subseteq\mathbb{R}^d\) be a bounded domain, and let \( \mathcal{T}\) be a regular triangulation of \( \Omega\) . Let \( f:\Omega\to\mathbb{R}\) be cpwl with respect to \( \mathcal{T}\) and \( f|_{\partial\Omega}=0\) . Then there exists a ReLU neural network \( \Phi:\Omega\to\mathbb{R}\) realizing \( f\) , and it holds

\[ \begin{align} {\rm size}(\Phi) = O(|\mathcal{T}|),~~ {\rm width}(\Phi)=O(|\mathcal{T}|),~~ {\rm depth}(\Phi) = O(1), \end{align} \]

(42)

\[ \begin{align} \\\end{align} \]

(43)

where the constants in the Landau notation depend on \( d\) and \( k_\mathcal{T}\) in (41).

We will split the proof into several lemmata. The strategy is to introduce a basis of the space of cpwl functions on \( \mathcal{T}\) the elements of which vanish on the boundary of \( \Omega\) . We will then show that there exist \( O(|\mathcal{T}|)\) basis functions, each of which can be represented with a neural network the size of which depends only on \( k_\mathcal{T}\) and \( d\) . To construct this basis, we first point out that an affine function on a simplex is uniquely defined by its values at the nodes.

Lemma 12

Let \( d \in \mathbb{N}\) . Let \( \tau\mathrm{:}= {\rm {co}}({\boldsymbol{\eta}}_0,\dots,{\boldsymbol{\eta}}_d)\) be a \( d\) -simplex. For every \( y_0,\dots,y_{d}\in\mathbb{R}\) , there exists a unique \( g\in\mathcal{P}_1(\mathbb{R}^d)\) such that \( g({\boldsymbol{\eta}}_i)=y_i\) , \( i=0,\dots,d\) .

Proof

Since \( {\boldsymbol{\eta}}_1-{\boldsymbol{\eta}}_0,\dots,{\boldsymbol{\eta}}_d-{\boldsymbol{\eta}}_0\) is a basis of \( \mathbb{R}^d\) , there is a unique \( {\boldsymbol{w}}\in\mathbb{R}^d\) such that \( {\boldsymbol{w}}^\top ({\boldsymbol{\eta}}_i-{\boldsymbol{\eta}}_0)=y_i-y_0\) for \( i=1,\dots,d\) . Then \( g({\boldsymbol{x}})\mathrm{:}= {\boldsymbol{w}}^\top{\boldsymbol{x}}+(y_0-{\boldsymbol{w}}^\top{\boldsymbol{\eta}}_0)\) is as desired. Moreover, for every \( g\in\mathcal{P}_1\) it holds that \( g(\sum_{i=0}^d\alpha_i{\boldsymbol{\eta}}_i)=\sum_{i=0}^d\alpha_ig({\boldsymbol{\eta}}_i)\) whenever \( \sum_{i=0}^d\alpha_i=1\) (this is in general not true if the coefficients do not sum to \( 1\) ). Hence, \( g\) is uniquely determined by its values at the nodes.

Since \( \Omega\) is the union of the simplices \( \tau\in\mathcal{T}\) , every cpwl function with respect to \( \mathcal{T}\) is thus uniquely defined through its values at the nodes. Hence, the desired basis consists of cpwl functions \( \varphi_{\boldsymbol{\eta}}:\Omega\to\mathbb{R}\) with respect to \( \mathcal{T}\) such that

\[ \begin{align} \varphi_{\boldsymbol{\eta}}({\boldsymbol{\mu}})=\delta_{{\boldsymbol{\eta}}{\boldsymbol{\mu}}}~~\text{ for all }{\boldsymbol{\mu}}\in\mathcal{V}, \end{align} \]

(44)

where \( \delta_{{\boldsymbol{\eta}}{\boldsymbol{\mu}}}\) denotes the Kronecker delta. Assuming \( \varphi_{\boldsymbol{\eta}}\) to be well-defined for the moment, we can then represent every cpwl function \( f:\Omega\to\mathbb{R}\) that vanishes on the boundary \( \partial\Omega\) as

\[ \begin{align*} f({\boldsymbol{x}}) = \sum_{{\boldsymbol{\eta}}\in\mathcal{V}\cap\mathring{\Omega}}f({\boldsymbol{\eta}})\varphi_{\boldsymbol{\eta}}({\boldsymbol{x}})~~\text{for all }{\boldsymbol{x}}\in\Omega. \end{align*} \]

Note that it suffices to sum over the set of interior nodes \( \mathcal{V}\cap\mathring{\Omega}\) , since \( f({\boldsymbol{\eta}})=0\) whenever \( {\boldsymbol{\eta}}\in\partial\Omega\) . To formally verify existence and well-definedness of \( \varphi_{\boldsymbol{\eta}}\) , we first need a lemma characterizing the boundary of so-called “patches” of the triangulation: For each \( {\boldsymbol{\eta}}\in\mathcal{V}\) , we introduce the patch \( \omega({\boldsymbol{\eta}})\) of the node \( {\boldsymbol{\eta}}\) as the union of all elements containing \( {\boldsymbol{\eta}}\) , i.e.,

\[ \begin{align} \omega({\boldsymbol{\eta}})\mathrm{:}= \bigcup_{\{\tau\in\mathcal{T}\,|\,{\boldsymbol{\eta}}\in\tau\}}\tau. \end{align} \]

(45)

Lemma 13

Let \( {\boldsymbol{\eta}}\in\mathcal{V}\cap\mathring{\Omega}\) be an interior node. Then,

\[ \begin{align*} \partial\omega({\boldsymbol{\eta}}) =\bigcup_{\{\tau\in\mathcal{T}\,|\,{\boldsymbol{\eta}}\in\tau\}}{\rm co}(V(\tau)\backslash\{{\boldsymbol{\eta}}\}). \end{align*} \]

We refer to Figure 13 for a visualization of Lemma 13. The proof of Lemma 13 is quite technical but nonetheless elementary. We therefore only outline the general argument but leave the details to the reader in Excercise 18: The boundary of \( \omega({\boldsymbol{\eta}})\) must be contained in the union of the boundaries of all \( \tau\) in the patch \( \omega({\boldsymbol{\eta}})\) . Since \( {\boldsymbol{\eta}}\) is an interior point of \( \Omega\) , it must also be an interior point of \( \omega({\boldsymbol{\eta}})\) . This can be used to show that for every \( S\mathrm{:}= \{{\boldsymbol{\eta}}_{i_0},\dots,{\boldsymbol{\eta}}_{i_{k}}\}\subseteq V(\tau)\) of cardinality \( k+1\le d\) , the interior of (the \( k\) -dimensional manifold) \( {\rm {co}}(S)\) belongs to the interior of \( \omega({\boldsymbol{\eta}})\) whenever \( {\boldsymbol{\eta}}\in S\) . Using Exercise 18, it then only remains to check that \( {\rm {co}}(S)\subseteq\partial\omega({\boldsymbol{\eta}})\) whenever \( {\boldsymbol{\eta}}\notin S\) , which yields the claimed formula. We are now in position to show well-definedness of the basis functions in (44).

Lemma 14

For each interior node \( {\boldsymbol{\eta}}\in\mathcal{V}\cap \mathring{\Omega}\) there exists a unique cpwl function \( \varphi_{{\boldsymbol{\eta}}}:\Omega\to\mathbb{R}\) satisfying (44). Moreover, \( \varphi_{{\boldsymbol{\eta}}}\) can be expressed by a ReLU neural network with size, width, and depth bounds that only depend on \( d\) and \( k_\mathcal{T}\) .

Proof

By Lemma 12, on each \( \tau\in\mathcal{T}\) , the affine function \( \varphi_{\boldsymbol{\eta}}|_{\tau}\) is uniquely defined through the values at the nodes of \( \tau\) . This defines a continuous function \( \varphi_{{\boldsymbol{\eta}}}:\Omega\to\mathbb{R}\) . Indeed, whenever \( \tau\cap\tau'\neq\emptyset\) , then \( \tau\cap\tau'\) is a subsimplex of both \( \tau\) and \( \tau'\) in the sense of Definition 12 (VI). Thus, applying Lemma 12 again, the affine functions on \( \tau\) and \( \tau'\) coincide on \( \tau\cap\tau'\) .

Using Lemma 12, Lemma 13 and the fact that \( \varphi_{{\boldsymbol{\eta}}}({\boldsymbol{\mu}})=0\) whenever \( {\boldsymbol{\mu}}\neq{\boldsymbol{\eta}}\) , we find that \( \varphi_{\boldsymbol{\eta}}\) vanishes on the boundary of the patch \( \omega({\boldsymbol{\eta}})\subseteq\Omega\) . Thus, \( \varphi_{\boldsymbol{\eta}}\) vanishes on the boundary of \( \Omega\) . Extending by zero, it becomes a cpwl function \( \varphi_{\boldsymbol{\eta}}:\mathbb{R}^d\to\mathbb{R}\) . This function is nonzero only on elements \( \tau\) for which \( {\boldsymbol{\eta}}\in\tau\) . Hence, it is a cpwl function with at most \( n\mathrm{:}= k_\mathcal{T}+1\) affine functions. By Theorem 6, \( \varphi_{\boldsymbol{\eta}}\) can be expressed as a ReLU neural network with the claimed size, width and depth bounds; to apply Theorem 6 we used that (the extension of) \( \varphi_{\boldsymbol{\eta}}\) is defined on the convex domain \( \mathbb{R}^d\) .

Finally, Theorem 7 is now an easy consequence of the above lemmata.

Proof (of Theorem 7)

With

\[ \begin{align} \Phi({\boldsymbol{x}})\mathrm{:}= \sum_{{\boldsymbol{\eta}}\in\mathcal{V}\cap\mathring{\Omega}} f({\boldsymbol{\eta}})\varphi_{\boldsymbol{\eta}}({\boldsymbol{x}}) ~~ \text{ for } {\boldsymbol{x}} \in \Omega, \end{align} \]

(46)

it holds that \( \Phi:\Omega\to\mathbb{R}\) satisfies \( \Phi({\boldsymbol{\eta}})=f({\boldsymbol{\eta}})\) for all \( {\boldsymbol{\eta}}\in\mathcal{V}\) . By Lemma 12 this implies that \( f\) equals \( \Phi\) on each \( \tau\) , and thus \( f\) equals \( \Phi\) on all of \( \Omega\) . Since each element \( \tau\) is the convex hull of \( d+1\) nodes \( {\boldsymbol{\eta}}\in\mathcal{V}\) , the cardinality of \( \mathcal{V}\) is bounded by the cardinality of \( \mathcal{T}\) times \( d+1\) . Thus, the summation in (46) is over \( O(|\mathcal{T}|)\) terms. Using Lemma 9 and Lemma 14 we obtain the claimed bounds on size, width, and depth of the neural network.

6.3.3 Size bounds for locally convex triangulations

Theorem 7 immediately implies convergence rates for certain classes of (low regularity) functions. Recall for example the space \( C^{0,s}\) of Hölder continuous functions.

Hölder continuous functions can be approximated well by cpwl functions. This leads to the following result.

The principle behind Theorem 9 can be applied in even more generality. Since we can represent every cpwl function on a regular triangulation with a neural network of size \( O(N)\) , where \( N\) denotes the number of elements, most classical (e.gfinite element) approximation theory for cpwl functions can be lifted to generate statements about ReLU approximation. For instance, it is well-known, that functions in the Sobolev space \( H^{2}([0,1]^d)\) can be approximated by cpwl functions on a regular triangulation in terms of \( L^2([0,1]^d)\) with the rate \( {2}/{d}\) , e.g., [8, Chapter 22]. Similar as in the proof of Theorem 9, for every \( f\in H^2([0,1]^d)\) and every \( N\in\mathbb{N}\) there then exists a ReLU neural network \( \Phi_N\) such that \( {\rm{size}}(\Phi_N)=O(N)\) and

Finally, we may consider how to approximate smoother functions such as \( f\in C^k([0,1]^d)\) , \( k>1\) , with ReLU neural networks. As discussed in Chapter 5 for sigmoidal activation functions, larger \( k\) can lead to faster convergence. However, we will see in the following chapter, that the emulation of piecewise affine functions on regular triangulations will not yield improved approximation rates as \( k\) increases. To leverage such smoothness with ReLU networks, in Chapter 8 we will first build networks that emulate polynomials. Surprisingly, it turns out that polynomials can be approximated very efficiently by deep ReLU neural networks.

The ReLU calculus introduced in Section 6.1 was similarly given in [1]. The fact that every cpwl function can be expressed as a maximum over a minimum of linear functions goes back to the papers [9, 4]; see also [5] for an accessible presentation of this result. Additionally, [6] provides sharper bounds on the number of required nestings in such representations.

The main result of Section 6.2, which shows that every cpwl function can be expressed by a ReLU network, is then a straightforward consequence. This was first observed in [2], which also provided bounds on the network size. These bounds were significantly improved in [3] for cpwl functions on triangular meshes that satisfy a local convexity condition. Under this assumption, it was shown that the network size essentially only grows linearly with the number of pieces. The paper [7] showed that the convexity assumption is not necessary for this statement to hold. We give a similar result in Section 6.3.2, using a simpler argument than [7]. The locally convex case from [3] is separately discussed in Section 6.3.3, as it allows for further improvements in some constants.

The implications for the approximation of Hölder continuous functions discussed in Section 6.4, follows by standard approximation theory for cpwl functions; see for example [10] or the finite element literature such as [11, 12, 8], which focus on approximation in Sobolev spaces. Additionally, [13] provide a stronger result, where it is shown that ReLU networks can essentially achieve twice the rate proven in Theorem 9, and this is sharp. For a general reference on splines and piecewise polynomial approximation see for instance [14]. Finally we mention that similar convergence results can also be shown for other activation functions, see, e.g., [15].

Neural networks are based on the composition and addition of neurons. These two operations increase the possible number of pieces in a very specific way. Figure 14 depicts the two operations and their effect. They can be described as follows:

• Summation: Let \( \Omega\subseteq\mathbb{R}\) . The sum of two cpwl functions \( f_1\) , \( f_2:\Omega\to\mathbb{R}\) satisfies

  \[ \begin{align} {\rm Pieces}(f_1 + f_2, \Omega) \leq {\rm Pieces}(f_1, \Omega) + {\rm Pieces}(f_2, \Omega)-1. \end{align} \]

  (53)

  This holds because the sum is affine in every point where both \( f_1\) and \( f_2\) are affine. Therefore, the sum has at most as many break points as \( f_1\) and \( f_2\) combined. Moreover, the number of pieces of a univariate function equals the number of its break points plus one.

• Composition: Let again \( \Omega \subseteq \mathbb{R}\) . The composition of two functions \( f_1 \colon \mathbb{R}^d \to \mathbb{R}\) and \( f_2\colon \Omega \to \mathbb{R}^d\) satisfies

  \[ \begin{align} {\rm Pieces}(f_1 \circ f_2, \Omega) \leq {\rm Pieces}(f_1, \mathbb{R}^d) \cdot {\rm Pieces}(f_2, \Omega). \end{align} \]

  (54)

  This is because for each of the affine pieces of \( f_2\) —let us call one of those pieces \( A \subseteq \mathbb{R}\) —we have that \( f_2\) is either constant or injective on \( A\) . If it is constant, then \( f_1 \circ f_2\) is constant. If it is injective, then \( \rm{ Pieces}(f_1 \circ f_2, A) = \rm{ Pieces}(f_1, f_2(A)) \leq \rm{ Pieces}(f_1, \mathbb{R}^d)\) . Since this holds for all pieces of \( f_2\) we get (54).

These considerations give the following result, which follows the argument of [2, Lemma 2.1]. We state it for general cpwl activation functions. The ReLU activation function corresponds to \( p=2\) . Recall that the notation \( (\sigma;d_0,\dots,d_{L+1})\) denotes the architecture of a feedforward neural network, see Definition 1.

Theorem 11 shows that there are limits to how many pieces can be created with a certain architecture. It is noteworthy that the effects of the depth and the width of a neural network are vastly different. While increasing the width can polynomially increase the number of pieces, increasing the depth can result in exponential increase. This is a first indication of the prowess of depth of neural networks.

To understand the effect of this on the approximation problem, we apply the bound of Theorem 11 to Theorem 10.

Theorem 12 gives a lower bound on achievable approximation rates in dependence of the depth \( L\) . As target functions become smoother, we expect that we can achieve faster convergence rates (cp. Chapter 5). However, without increasing the depth, it seems to be impossible to leverage such additional smoothness.

This observation strongly indicates that deeper architectures can be superior. Before making this more concrete, we first explore whether the upper bounds of Theorem 11 are also achievable.

We follow [2] to construct a ReLU neural network, that realizes the upper bound of Theorem 11. First let \( h_1:[0,1]\to\mathbb{R}\) be the hat function

This function can be expressed by a ReLU neural network of depth one and with two nodes

i.e., \( h_n=h_1\circ…\circ h_1\) is the \( n\) -fold composition of \( h_1\) . Since \( h_1:[0,1]\to [0,1]\) , we have \( h_n:[0,1]\to [0,1]\) and

It turns out that this function has a rather interesting behavior. It is a “sawtooth” function with \( 2^{n-1}\) spikes, see Figure 15.

The neural network \( h_n\) has size \( O(n)\) and is piecewise linear on at least \( 2^n\) pieces. This shows that the number of pieces can indeed increase exponentially in the neural network size, also see the upper bound in Theorem 11.

We have seen in Theorem 11 that deep neural networks can have many more pieces than their shallow counterparts. This begs the question if deep neural networks tend to generate more pieces in practice. More formally: If we randomly initialize the weights of a neural network, what is the expected number of linear regions? Will this number scale exponentially with the depth? This question was analyzed in [3], and surprisingly, it was found that the number of pieces of randomly initialized neural networks typically does not depend exponentially on the depth. In Figure 16, we depict two neural networks, one shallow and one deep, that were randomly initialized according to He initialization [4]. Both neural networks have essentially the same number of pieces (\( 114\) and \( 110\) ) and there is no clear indication that one has a deeper architecture than the other.

In the following, we will give a simplified version of the main result of [3] to show why random deep neural networks often behave like shallow neural networks.

We recall from Figure 14 that pieces are generated through composition of two functions \( f_1\) and \( f_2\) , if the values of \( f_2\) cross a level that is associated to a break point of \( f_1\) . In the case of a simple neuron of the form

where \( h\) is a cpwl function, \( {\boldsymbol{a}}\) is a vector, and \( b\) is a scalar, many pieces can be generated if \( \langle{\boldsymbol{a}}, h({\boldsymbol{x}}) \rangle \) crosses the \( -b\) level often.

If \( {\boldsymbol{a}}\) , \( b\) are random variables, and we know that \( h\) does not oscillate too much, then we can quantify the probability of \( \langle {\boldsymbol{a}}, h({\boldsymbol{x}}) \rangle \) crossing the \( -b\) level often. The following lemma from [5, Lemma 3.1] provides the details.

Lemma 18 applied to neural networks essentially states that, in a single neuron, if the bias term is chosen uniformly randomly on an interval of length \( \delta\) , then the probability of generating at least \( t\) pieces by composition scales reciprocal to \( t\) .

Next, we will analyze how Lemma 18 implies an upper bound on the number of pieces generated in a randomly initialized neural network. For simplicity, we only consider random biases in the following, but mention that similar results hold if both the biases and weights are random variables [3].

To apply Lemma 18 to a single neuron with random biases, we also need some bound on the derivative of the input to the neuron.

We can now formulate the main result of this section.

Establishing bounds on the number of linear regions of a ReLU network has been a popular tool to investigate the complexity of ReLU neural networks, see [6, 7, 8, 9, 3]. The bound presented in Section 7.1, is based on [2]. For the construction of the sawtooth function in Section 7.2, we follow the arguments in [2, 10]. Together with the lower bound on the number of required linear regions given in [1], this analysis shows how depth can be a limiting factor in terms of achievable convergence rates, as stated in Theorem 12. Finally, the analysis of the number of pieces deep neural networks attained with random intialization (Section 7.3) is based on [3] and [5].

We start with the approximation of the map \( x\mapsto x^2\) . The construction, first given in [1], is based on the sawtooth functions \( h_n\) defined in (59) and originally introduced in [2], see Figure 15. The proof idea is visualized in Figure 19.

As a consequence there holds the following, [1, Proposition 2].

In conclusion, we have shown that \( s_n:[0,1]\to [0,1]\) approximates the square function uniformly on \( [0,1]\) with exponentially decreasing error in the neural network size. Note that due to Theorem 12, this would not be possible with a shallow neural network, which can at best interpolate \( x^2\) on a partition of \( [0,1]\) with polynomially many (w.r.tthe neural network size) pieces.

According to Lemma 19, depth can help in the approximation of \( x\mapsto x^2\) , which, on first sight, seems like a rather specific example. However, as we shall discuss in the following, this opens up a path towards fast approximation of functions with high regularity, e.g., \( C^k([0,1]^d)\) for some \( k>1\) . The crucial observation is that, via the polarization identity we can write the product of two numbers as a sum of squares

for all \( x\) , \( y\in\mathbb{R}\) . Efficient approximation of the operation of multiplication allows efficient approximation of polynomials. Those in turn are well-known to be good approximators for functions exhibiting \( k\in\mathbb{N}\) derivatives. Before exploring this idea further in the next section, we first make precise the observation that neural networks can efficiently approximate the multiplication of real numbers.

We start with the multiplication of two numbers, in which case neural networks of logarithmic size in the desired accuracy are sufficient, [1, Proposition 3].

In a similar way as in Proposition 6 and Lemma 11, we can apply operations with two inputs in the form of a binary tree to extend them to an operation on arbitrary many inputs; see again [1], and [3, Proposition 3.3] for the specific argument considered here.

As a first consequence of the above observations, we consider approximating the polynomial

One possibility to approximate \( p\) is via the Horner scheme and the approximate multiplication \( \Phi^{\times}_\varepsilon\) from Lemma 20, yielding

This scheme requires depth \( O(n)\) due to the nested multiplications. An alternative is to approximate all monomials \( 1,x,\dots,x^n\) with a binary tree using approximate multiplications \( \Phi_\varepsilon^\times\) , and combing them in the output layer, see Figure 21. This idea leads to a network of size \( O(n\log(n))\) and depth \( O(\log(n))\) . The following lemma formalizes this, see [4, Lemma A.5], [5, Proposition III.5], and in particular [6, Lemma 4.3]. The proof is left as Exercise 24.

Lemma 21 shows that deep ReLU networks can approximate polynomials efficiently. This leads to an interesting implication regarding the superiority of deep architectures. Recall that \( f:[-1,1]\to\mathbb{R}\) is analytic if its Taylor series around any point \( x\in [-1,1]\) converges to \( f\) in a neighbourhood of \( x\) . For instance all polynomials, \( \sin\) , \( \cos\) , \( \exp\) etcare analytic. We now show that these functions (except linear ones) can be approximated much more efficiently with deep ReLU networks than by shallow ones: for fixed-depth networks, the number of parameters must grow faster than any polynomial compared to the required size of deep architectures. More precisely there holds the following.

The proposition shows that the approximation of certain (highly relevant) functions requires significantly more parameters when using shallow instead of deep architectures. Such statements are known as depth separation results. We refer for instance to [2, 7, 8], where such a result was shown by Telgarsky based on the sawtooth function constructed in Section 7.2. Lower bounds on the approximation in the spirit of Proposition 10 were also given in [9] and [1].

We will now discuss the implications of our observations in the previous sections for the approximation of functions in the class \( C^{k,s}\) .

Note that these spaces are ordered according to

for all \( 0<s\le t\le 1\) .

In order to state our main result, we first recall a version of Taylor’s remainder formula for \( C^{k,s}(\Omega)\) functions.

We now come to the main statement of this section. Up to logarithmic terms, it shows the convergence rate \( (k+s)/{d}\) for approximating functions in \( C^{k,s}([0,1]^d)\) .

Theorem 14 is similar in spirit to [1, Section 3.2]; the main differences are that [1] considers the class \( C^k([0,1]^d)\) instead of \( C^{k,s}([0,1]^d)\) , and uses an approximate partition of unity, while we use the exact partition of unity constructed in Chapter 6. Up to logarithmic terms, the theorem shows the convergence rate \( (k+s)/{d}\) . As long as \( k\) is large, in principle we can achieve arbitrarily large (and \( d\) -independent if \( k\ge d\) ) convergence rates. In contrast to Theorem 9, achieving error \( N^{-\frac{k+s}{d}}\) requires depth \( O(\log(N))\) , i.ethe neural network depth is required to increase. This can be avoided however, and networks of depth \( O(k/d)\) suffice to attain these convergence rates [4].

This chapter is based on the seminal 2017 paper by Yarotsky [1], where the construction of approximating the square function, the multiplication, and polynomials (discussed in Sections 8.1, 8.2, 8.3) was first introduced and analyzed. The construction relies on the sawtooth function discussed in Section 7.2 and originally constructed by Telgarsky in [2]. Similar results were obtained around the same time by Liang and Srikant via a bit extraction technique using both the ReLU and the Heaviside function as activation functions [9]. These works have since sparked a large body of research, as they allow to lift polynomial approximation theory to neural network classes. Convergence results based on this type of argument include for example [4, 12, 13, 10, 11]. We also refer to [14] for related results on rational approximation.

The depth separation result in Section 8.3 is based on the exponential convergence rates obtained for analytic functions in [10, 11], also see [5, Lemma III.7]. For the approximation of polynomials with ReLU neural networks stated in Lemma 21, see, e.g., [4, 5, 6], and also [15, 16] for constructions based on Chebyshev polynomials, which can be more efficient. For further depth separation results, we refer to [2, 7, 17, 18, 19]. Moreover, closely related to such statements is the 1987 thesis by Håstad [15], which considers the limitations of logic circuits in terms of depth.

The approximation result derived in Section 8.4 for \( C^{k,s}\) functions follows by standard approximation theory for piecewise polynomial functions, and is similar as in [1]. We point out that such statements can also be shown for other activation functions than ReLU; see in particular the works of Mhaskar [20, 21] and Section 6 in Pinkus’ Acta Numerica article [22] for sigmoidal and smooth activations. Additionally, the more recent paper [23] specifically addresses the hyperbolic tangent activation. Finally, [24] studies general activation functions that allow for the construction of approximate partitions of unity.

In [105], Barron introduced a set of functions that can be approximated by neural networks without a curse of dimensionality. This set, known as the Barron class, is characterized by a specific type of bounded variation. To define it, for \( g\in L^1(\mathbb{R}^d)\) we denote by

its inverse Fourier transform. Then, for \( C>0\) the Barron class is defined as

We say that a function \( f \in \Gamma_C\) has a finite Fourier moment, even though technically the Fourier transform of \( f\) may not be well-defined, since \( f\) does not need to be integrable. By the Riemann-Lebesgue Lemma, [106, Lemma 1.1.1], the condition \( f\in C(\mathbb{R}^d)\) in the definition of \( \Gamma_{C}\) is automatically satisfied if \( g \in L^1(\mathbb{R}^d)\) as in the definition exists.

The following proof approximation result for functions in \( \Gamma_C\) is due to [105]. The presentation of the proof is similar to [107, Section 5].

Importantly, the dimension \( d\) does not enter on the right-hand side of (73), in particular the convergence rate is not directly affected by the dimension, which is in stark contrast to the results of the previous chapters. However, it should be noted, that the constant \( C\) may still have some inherent \( d\) -dependence, see Exercise 29.

The proof of Theorem 15 is based on a peculiar property of high-dimensional convex sets, which is described by the (approximate) Carathéodory theorem, the original version of which was given in [1]. The more general version stated in the following lemma follows [2, Theorem 0.0.2] and [3, 4]. For its statement recall that \( \overline{\rm{ co}}(G)\) denotes the the closure of the convex hull of \( G\) .

Lemma 23 provides a powerful tool: If we want to approximate a function \( f\) with a superposition of \( N\) elements in a set \( G\) , then it is sufficient to show that \( f\) can be represented as an arbitrary (infinite) convex combination of elements of \( G\) .

Lemma 23 suggests that we can prove Theorem 15 by showing that each function in \( \Gamma_C\) belongs to the closure of the convex hull of all neural networks with a single neuron, i.ethe set of all affine transforms of the sigmoidal activation function \( \sigma\) . We make a small detour before proving this result. We first show that each function \( f \in \Gamma_C\) is in the closure of the convex hull of the set of affine transforms of Heaviside functions, i.ethe set

The following lemma, corresponding to [105, Theorem 2] and [107, Lemma 5.12], provides a link between \( \Gamma_C\) and \( G_C\) .

We now have all tools to complete the proof of Theorem 15.

The dimension-independent approximation rate of Theorem 15 may seem surprising, especially when comparing to the results in Chapters 5 and 6. However, this can be explained by recognizing that the assumption of a finite Fourier moment is effectively a dimension-dependent regularity assumption. Indeed, the condition becomes more restrictive in higher dimensions and hence the complexity of \( \Gamma_C\) does not grow with the dimension.

To further explain this, let us relate the Barron class to classical function spaces. In [105, Section II] it was observed that a sufficient condition is that all derivatives of order up to \( \lfloor d/2 \rfloor +2\) are square-integrable. In other words, if \( f\) belongs to the Sobolev space \( H^{\lfloor d/2 \rfloor +2}(\mathbb{R}^d)\) , then \( f\) is a Barron function. Importantly, the functions must become smoother, as the dimension increases. This assumption would also imply an approximation rate of \( N^{-1/2}\) in the \( L^2\) norm by sums of at most \( N\) B-splines, see [53, 103]. However, in such estimates some constants may still depend exponentially on \( d\) , whereas all constants in Theorem 15 are controlled independently of \( d\) .

Another notable aspect of the approximation of Barron functions is that the absolute values of the weights other than the output weights are not bounded by a constant. To see this, we refer to (81), where arbitrarily large \( \theta\) need to be used. While \( \Gamma_C\) is a compact set, the set of neural networks of the specified architecture for a fixed \( N\in \mathbb{N}\) is not parameterized with a compact parameter set. In a certain sense, this is reminiscent of Proposition 4 and Theorem 3, where arbitrarily strong approximation rates where achieved by using a very complex activation function and a non-compact parameter space.

As a next instance of types of functions for which the curse of dimensionality can be overcome, we study functions with compositional structure. In words, this means that we study high-dimensional functions that are constructed by composing many low-dimensional functions. This point of view was proposed in [112]. Note that this can be a realistic assumption in many cases, such as for sensor networks, where local information is first aggregated in smaller clusters of sensors before some information is sent to a processing unit for further evaluation.

We introduce a model for compositional functions next. Consider a directed acyclic graph \( \mathcal{G}\) with \( M\) vertices \( \eta_1,\dots,\eta_M\) such that

• exactly \( d\) vertices, \( \eta_1,\dots,\eta_d\) , have no ingoing edge,
• each vertex has at most \( m\in\mathbb{N}\) ingoing edges,
• exactly one vertex, \( \eta_M\) , has no outgoing edge.

With each vertex \( \eta_j\) for \( j>d\) we associate a function \( f_j:\mathbb{R}^{d_j}\to\mathbb{R}\) . Here \( d_j\) denotes the cardinality of the set \( S_j\) , which is defined as the set of indices \( i\) corresponding to vertices \( \eta_i\) for which we have an edge from \( \eta_i\) to \( \eta_j\) . Without loss of generality, we assume that \( m\ge d_j=|S_j|\ge 1\) for all \( j>d\) . Finally, we let

Then \( F_M(x_1,\dots,x_d)\) is a function from \( \mathbb{R}^d\to\mathbb{R}\) . Assuming

we denote the set of all functions of the type \( F_M\) by \( \mathcal{F}^{k,s}(m,d,M)\) . Figure 22 shows possible graphs of such functions.

Clearly, for \( s=0\) , \( \mathcal{F}^{k,0}(m,d,M)\subseteq C^{k}(\mathbb{R}^d)\) since the composition of functions in \( C^k\) belongs again to \( C^k\) . A direct application of Theorem 14 allows to approximate \( F_M\in \mathcal{F}^{k}(m,d,M)\) with a neural network of size \( O(N\log(N))\) and error \( O(N^{-\frac{k}{d}})\) . Since each \( f_j\) depends only on \( m\) variables, intuitively we expect an error convergence of type \( O(N^{-\frac{k}{m}})\) with the constant somehow depending on the number \( M\) of vertices. To show that this is actually possible, in the following we associate with each node \( \eta_j\) a depth \( l_j\ge 0\) , such that \( l_j\) is the maximum number of edges connecting \( \eta_j\) to one of the nodes \( \{\eta_1,\dots,\eta_d\}\) .

Another instance in which the curse of dimension can be mitigated, is if the input to the network belongs to \( \mathbb{R}^d\) , but stems from an \( m\) -dimensional manifold \( \mathcal{M}\subseteq\mathbb{R}^d\) . If we only measure the approximation error on \( \mathcal{M}\) , then we can again show that it is \( m\) rather than \( d\) that determines the rate of convergence.

To explain the idea, we assume in the following that \( \mathcal{M}\) is a smooth, compact \( m\) -dimensional manifold in \( \mathbb{R}^d\) . Moreover, we suppose that there exists \( \delta>0\) and finitely many points \( {\boldsymbol{x}}_1,\dots,{\boldsymbol{x}}_M\in\mathcal{M}\) such that the \( \delta\) -balls \( B_{\delta/2}({\boldsymbol{x}}_i)\mathrm{:}= \{{\boldsymbol{y}}\in\mathbb{R}^d\,|\,\| {\boldsymbol{y}}-{\boldsymbol{x}} \|_{2}<{\delta}/{2}\}\) for \( j=1,\dots,M\) cover \( \mathcal{M}\) (for every \( \delta>0\) such \( {\boldsymbol{x}}_i\) exist since \( \mathcal{M}\) is compact). Moreover, denoting by \( T_{{\boldsymbol{x}}}\mathcal{M}\simeq \mathbb{R}^m\) the tangential space of \( \mathcal{M}\) at \( {\boldsymbol{x}}\) , we assume \( \delta>0\) to be so small that the orthogonal projection

is injective, the set \( \pi_j(B_{\delta}({\boldsymbol{x}}_j)\cap\mathcal{M})\subseteq T_{{\boldsymbol{x}}_j}\mathcal{M}\) has \( C^\infty\) boundary, and the inverse of \( \pi_j\) , i.e.

is \( C^\infty\) (this is possible because \( \mathcal{M}\) is a smooth manifold). A visualization of this assumption is shown in Figure 23.

Note that \( \pi_j\) in (90) is a linear map, whereas \( \pi_j^{-1}\) in (91) is in general non-linear.

For a function \( f:\mathcal{M}\to\mathbb{R}\) we can then write

where

In the following, for \( f:\mathcal{M}\to\mathbb{R}\) , \( k\in\mathbb{N}_0\) , and \( s\in [0,1)\) we let

We now state the main result of this section.

The ideas of Section 9.1 were originally developed in [105], with an extension to \( L^\infty\) approximation provided in [114]. These arguments can be extended to yield dimension-independent approximation rates for high-dimensional discontinuous functions, provided the discontinuity follows a Barron function, as shown in [107]. The Barron class has been generalized in various ways, as discussed in [115, 116, 117, 118, 119].

The compositionality assumption of Section 9.2 was discussed in the form presented in [112]. An alternative approach, known as the hierarchical composition/interaction model, was studied in [120].

The manifold assumption discussed in Section 9.3 is frequently found in the literature, with notable examples including [121, 122, 123, 124, 125, 126].

Another prominent direction, omitted in this chapter, pertains to scientific machine learning. High-dimensional functions often arise from (parametric) PDEs, which have a rich literature describing their properties and structure. Various results have shown that neural networks can leverage the inherent low-dimensionality known to exist in such problems. Efficient approximation of certain classes of high-dimensional (or even infinite-dimensional) analytic functions, ubiquitous in parametric PDEs, has been verified in [86, 127]. Further general analyses for high-dimensional parametric problems can be found in [128, 129], and results exploiting specific structural conditions of the underlying PDEs, e.g., in [130, 131]. Additionally, [90, 93, 91] provide results regarding fast convergence for certain smooth functions in potentially high but finite dimensions.

For high-dimensional PDEs, elliptic problems have been addressed in [132], linear and semilinear parabolic evolution equations have been explored in [133, 134, 135], and stochastic differential equations in [136, 137].

Under what conditions on the activation function and architecture can a set of neural networks interpolate \( m \in \mathbb{N}\) points? According to Chapter 4, particularly Theorem 2, we know that shallow neural networks can approximate every continuous function with arbitrary accuracy, provided the neural network width is large enough. As the neural network’s width and/or depth increases, the architectures become increasingly powerful, leading us to expect that at some point, they should be able to interpolate \( m\) points. However, this intuition may not be correct:

Moreover, Theorem 2 is an asymptotic result that only states that a given function can be approximated for sufficiently large neural network architectures, but it does not state how large the architecture needs to be.

Surprisingly, Theorem 2 can nonetheless be used to give a guarantee that a fixed-size architecture yields sets of neural networks that allow the interpolation of \( m\) points. This result is due to [1]; for a more detailed discussion of previous results see the bibliography section. Due to its similarity to the universal approximation theorem and the fact that it uses the same assumptions, we call the following theorem the “Universal Interpolation Theorem”. For its statement recall the definition of the set of allowed activation functions \( \mathcal{M}\) in (8) and the class \( \mathcal{N}_d^1(\sigma,1,n)\) of shallow neural networks of width \( n\) introduced in Definition 5.

Consider a bounded domain \( \Omega\subseteq\mathbb{R}^d\) , a function \( f:\Omega\to\mathbb{R}\) , distinct points \( {\boldsymbol{x}}_1,\dots,{\boldsymbol{x}}_m\in \Omega\) , and corresponding function values \( y_i\mathrm{:}= f({\boldsymbol{x}}_i)\) . Our objective is to approximate \( f\) based solely on the data pairs \( ({\boldsymbol{x}}_i,y_i)\) , \( i=1,\dots,m\) . In this section, we will show that, under certain assumptions on \( f\) , ReLU neural networks can express an “optimal” reconstruction which also turns out to be an interpolant of the data.

10.2.1 Motivation

In the previous section, we observed that neural networks with \( m-1\in \mathbb{N}\) hidden neurons can interpolate \( m\) points for every reasonable activation function. However, not all interpolants are equally suitable for a given application. For instance, consider Figure 24 for a comparison between polynomial and piecewise affine interpolation on the unit interval.

The two interpolants exhibit rather different behaviors. In general, there is no way of determining which constitutes a better approximation to \( f\) . In particular, given our limited information about \( f\) , we cannot accurately reconstruct any additional features that may exist between interpolation points \( {\boldsymbol{x}}_1,\dots,{\boldsymbol{x}}_m\) . In accordance with Occam’s razor, it thus seems reasonable to assume that \( f\) does not exhibit extreme oscillations or behave erratically between interpolation points. As such, the piecewise interpolant appears preferable in this scenario. One way to formalize the assumption that \( f\) does not “exhibit extreme oscillations” is to assume that the Lipschitz constant

\[ \begin{align} {\rm Lip}(f):=\sup_{{\boldsymbol{x}}\neq {\boldsymbol{y}}}\frac{|f({\boldsymbol{x}})-f({\boldsymbol{y}})|}{\| {\boldsymbol{x}}-{\boldsymbol{y}} \|_{}} \end{align} \]

(105)

of \( f\) is bounded by a fixed value \( M\in\mathbb{R}\) . Here \( \| \cdot \|_{}\) denotes an arbitrary fixed norm on \( \mathbb{R}^d\) .

How should we choose \( M\) ? For every function \( f:\Omega\to\mathbb{R}\) satisfying

\[ \begin{align} f({\boldsymbol{x}}_i)=y_i~\text{ for all }~ i=1,\dots,m, \end{align} \]

(106)

we have

\[ \begin{align} {\rm Lip}(f) = \sup_{{\boldsymbol{x}}\neq {\boldsymbol{y}}\in\Omega} \frac{|f({\boldsymbol{x}}) - f({\boldsymbol{y}})|}{\| {\boldsymbol{x}}-{\boldsymbol{y}} \|_{}} \geq \sup_{i \neq j} \frac{|y_i - y_j|}{\| {\boldsymbol{x}}_i - {\boldsymbol{x}}_j \|_{}} \mathrm{:=} \tilde M. \end{align} \]

(107)

Because of this, we fix \( M\) as a real number greater than or equal to \( \tilde M\) for the remainder of our analysis.

10.2.2 Optimal reconstruction for Lipschitz continuous functions

The above considerations raise the following question: Given only the information that the function has Lipschitz constant at most \( M\) , what is the best reconstruction of \( f\) based on the data? We consider here the “best reconstruction” to be a function that minimizes the \( L^\infty\) -error in the worst case. Specifically, with

\[ \begin{align} {\rm Lip}_M(\Omega) \mathrm{:}=\{f:\Omega\to\mathbb{R}\,|\,{\rm Lip}(f)\le M\}, \end{align} \]

(108)

denoting the set of all functions with Lipschitz constant at most \( M\) , we want to solve the following problem:

Problem 1

We wish to find an element

\[ \begin{align} \Phi\in {\rm argmin}_{h:\Omega\to\mathbb{R}}~\sup_{\substack{f \in {\rm Lip}_M(\Omega)\\ \text{\( f\) satisfies (98)}}} ~\sup_{{\boldsymbol{x}}\in\Omega}|f({\boldsymbol{x}})-h({\boldsymbol{x}})|. \end{align} \]

(109)

The next theorem shows that a function \( \Phi\) as in (109) indeed exists. This \( \Phi\) not only allows for an explicit formula, it also belongs to \( {\rm{Lip}}_M(\Omega)\) and additionally interpolates the data. Hence, it is not just an optimal reconstruction, it is also an optimal interpolant. This theorem goes back to [2], which, in turn, is based on [3].

Theorem 17

Let \( m\) , \( d \in \mathbb{N}\) , \( \Omega\subseteq\mathbb{R}^d\) , \( f:\Omega\to\mathbb{R}\) , and let \( {\boldsymbol{x}}_1,\dots,{\boldsymbol{x}}_m \in \Omega\) , \( y_1,\dots,y_m\in \mathbb{R}\) satisfy (106) and (107) with \( \tilde{M} \ge 0\) . Further, let \( M\geq \tilde{M}\) .

Then, Problem 1 has at least one solution given by

\[ \begin{align} \Phi({\boldsymbol{x}}):=\frac{1}{2}(f_{\rm upper}({\boldsymbol{x}})+f_{\rm lower}({\boldsymbol{x}})) ~~ \text{ for } {\boldsymbol{x}} \in \Omega, \end{align} \]

(110)

where

\[ \begin{align*} f_{\rm upper}({\boldsymbol{x}})&\mathrm{:}= \min_{k=1,\dots,m}(y_k+M\| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{})\\ f_{\rm lower}({\boldsymbol{x}})&\mathrm{:}= \max_{k=1,\dots,m}(y_k-M\| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{}). \end{align*} \]

Moreover, \( \Phi\in{{\rm {Lip}}}_M(\Omega)\) and \( \Phi\) interpolates the data (i.esatisfies (106)).

Proof

First we claim that for all \( h_1\) , \( h_2\in{{\rm {Lip}}}_M(\Omega)\) holds \( \max\{h_1,h_2\}\in {\rm{Lip}}_M(\Omega)\) as well as \( \min\{h_1,h_2\}\in {\rm{Lip}}_M(\Omega)\) . Since \( \min\{h_1,h_2\}=-\max\{-h_1,-h_2\}\) , it suffices to show the claim for the maximum. We need to check that

\[ \begin{align} \frac{|\max\{h_1({\boldsymbol{x}}),h_2({\boldsymbol{x}})\}-\max\{h_1({\boldsymbol{y}}),h_2({\boldsymbol{y}})\}|}{\| {\boldsymbol{x}}-{\boldsymbol{y}} \|_{}}\le M \end{align} \]

(111)

for all \( {\boldsymbol{x}}\neq{\boldsymbol{y}}\in\Omega\) . Fix \( {\boldsymbol{x}}\neq{\boldsymbol{y}}\) . Without loss of generality we assume that

\[ \begin{align*} \max\{h_1({\boldsymbol{x}}),h_2({\boldsymbol{x}})\}\ge \max\{h_1({\boldsymbol{y}}),h_2({\boldsymbol{y}})\}~\text{and}~ \max\{h_1({\boldsymbol{x}}),h_2({\boldsymbol{x}})\}=h_1({\boldsymbol{x}}). \end{align*} \]

If \( \max\{h_1({\boldsymbol{y}}),h_2({\boldsymbol{y}})\}=h_1({\boldsymbol{y}})\) then the numerator in (111) equals \( h_1({\boldsymbol{x}})-h_1({\boldsymbol{y}})\) which is bounded by \( M\| {\boldsymbol{x}}-{\boldsymbol{y}} \|_{}\) . If \( \max\{h_1({\boldsymbol{y}}),h_2({\boldsymbol{y}})\}=h_2({\boldsymbol{y}})\) , then the numerator equals \( h_1({\boldsymbol{x}})-h_2({\boldsymbol{y}})\) which is bounded by \( h_1({\boldsymbol{x}})-h_1({\boldsymbol{y}})\le M\| {\boldsymbol{x}}-{\boldsymbol{y}} \|_{}\) . In either case (111) holds.

Clearly, \( {\boldsymbol{x}}\mapsto y_k-M\| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{}\in{{\rm {Lip}}}_M(\Omega)\) for each \( k=1,\dots,m\) and thus \( f_{\rm{upper}}\) , \( f_{\rm{lower}}\in{{\rm Lip}}_M(\Omega)\) as well as \( \Phi\in{{\rm {Lip}}}_M(\Omega)\) .

Next we claim that for all \( f\in{{\rm {Lip}}}_M(\Omega)\) satisfying (106) holds

\[ \begin{align} f_{\rm lower}({\boldsymbol{x}})\le f({\boldsymbol{x}})\le f_{\rm upper}({\boldsymbol{x}})~\text{ for all } ~ {\boldsymbol{x}}\in\Omega. \end{align} \]

(112)

This is true since for every \( k\in\{1,\dots,m\}\) and \( {\boldsymbol{x}}\in\Omega\)

\[ \begin{align*} |y_k-f({\boldsymbol{x}})| = |f({\boldsymbol{x}}_k)-f({\boldsymbol{x}})|\le M \| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{} \end{align*} \]

so that for all \( {\boldsymbol{x}}\in\Omega\)

\[ \begin{align*} f({\boldsymbol{x}})\le \min_{k=1,\dots,m}(y_k+M\| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{}),~~ f({\boldsymbol{x}})\ge \max_{k=1,\dots,m}(y_k-M\| {\boldsymbol{x}}-{\boldsymbol{x}}_k \|_{}). \end{align*} \]

Since \( f_{\rm{upper}}\) , \( f_{\rm{lower}}\in{{\rm Lip}}_M(\Omega)\) satisfy (106), we conclude that for every \( h:\Omega\to\mathbb{R}\) holds

\[ \begin{align} \sup_{\substack{f\in{\rm Lip}_M(\Omega)\\ \text{\( f\) satisfies (98)}}}\sup_{{\boldsymbol{x}}\in\Omega}|f({\boldsymbol{x}})-h({\boldsymbol{x}})| &\ge \sup_{{\boldsymbol{x}}\in\Omega} \max\{|f_{\rm lower}({\boldsymbol{x}})-h({\boldsymbol{x}})|,|f_{\rm upper}({\boldsymbol{x}})-h({\boldsymbol{x}})|\}\nonumber \end{align} \]

(113)

\[ \begin{align} & \ge \sup_{{\boldsymbol{x}}\in\Omega} \frac{|f_{\rm lower}({\boldsymbol{x}}) - f_{\rm upper}({\boldsymbol{x}})|}{2}. \end{align} \]

(114)

\[ \begin{align} \end{align} \]

(115)

\[ \begin{align} \\\end{align} \]

(116)

Moreover, using (112),

\[ \begin{align} \sup_{\substack{f\in{\rm Lip}_M(\Omega)\\ \text{\( f\) satisfies (98)}}}\sup_{{\boldsymbol{x}}\in\Omega}|f({\boldsymbol{x}})-\Phi({\boldsymbol{x}})|&\le \sup_{{\boldsymbol{x}}\in\Omega} \max\{|f_{\rm lower}({\boldsymbol{x}})-\Phi({\boldsymbol{x}})|,|f_{\rm upper}({\boldsymbol{x}})-\Phi({\boldsymbol{x}})|\} \nonumber \end{align} \]

(117)

\[ \begin{align} &= \sup_{{\boldsymbol{x}}\in\Omega} \frac{|f_{\rm lower}({\boldsymbol{x}}) - f_{\rm upper}({\boldsymbol{x}})|}{2}. \end{align} \]

(118)

\[ \begin{align} \end{align} \]

(119)

\[ \begin{align} \\\end{align} \]

(120)

Finally, (113) and (117) imply that \( \Phi\) is a solution of Problem 1.

Figure 25 depicts \( f_{\rm{upper}}\) , \( f_{\rm{lower}}\) , and \( \Phi\) for the interpolation problem shown in Figure 24, while Figure 26 provides a two-dimensional example.

10.2.3 Optimal ReLU reconstructions

So far everything was valid with an arbitrary norm on \( \mathbb{R}^d\) . For the next theorem, we will restrict ourselves to the \( 1\) -norm \( \| {\boldsymbol{x}} \|_{1}=\sum_{j=1}^d|x_j|\) . Using the explicit formula of Theorem 17, we will now show the remarkable result that ReLU neural networks can exactly express an optimal reconstruction (in the sense of Problem 1) with a neural network whose size scales linearly in the product of the dimension \( d\) and the number of data points \( m\) . Additionally, the proof is constructive, thus allowing in principle for an explicit construction of the neural network without the need for training.

Theorem 18 (Optimal Lipschitz Reconstruction)

Let \( m\) , \( d \in \mathbb{N}\) , \( \Omega\subseteq\mathbb{R}^d\) , \( f:\Omega\to\mathbb{R}\) , and let \( {\boldsymbol{x}}_1,\dots,{\boldsymbol{x}}_m \in \Omega\) , \( y_1,\dots,y_m\in \mathbb{R}\) satisfy (106) and (107) with \( \tilde{M} > 0\) . Further, let \( M\geq \tilde{M}\) and let \( \| \cdot \|_{}=\| \cdot \|_{1}\) in (107) and (108).

Then, there exists a ReLU neural network \( \Phi \in {\rm{Lip}}_M(\Omega)\) that interpolates the data (i.esatisfies (106)) and satisfies

\[ \begin{align*} \Phi \in {\rm argmin}_{h:\Omega\to\mathbb{R}} \sup_{\substack{f \in {\rm Lip}_M(\Omega)\\ \text{\( f\) satisfies (98)}}} \sup_{{\boldsymbol{x}}\in\Omega}|f({\boldsymbol{x}})-h({\boldsymbol{x}})|. \end{align*} \]

Moreover, \( {\rm{depth}}(\Phi)=O(\log(m))\) , \( {\rm{width}}(\Phi)=O(dm)\) and all weights of \( \Phi\) are bounded in absolute value by \( \max\{M,\| {\boldsymbol{y}} \|_{\infty}\}\) .

Proof

To prove the result, we simply need to show that the function in (110) can be expressed as a ReLU neural network with the size bounds described in the theorem. First we notice, that there is a simple ReLU neural network that implements the 1-norm. It holds for all \( {\boldsymbol{x}} \in \mathbb{R}^d\) that

\[ \begin{align*} \| {\boldsymbol{x}} \|_{1} = \sum_{i=1}^d \left(\sigma(x_i) + \sigma(-x_i)\right). \end{align*} \]

Thus, there exists a ReLU neural network \( \Phi^{\| \cdot \|_{1}}\) such that for all \( {\boldsymbol{x}}\in\mathbb{R}^d\)

\[ \begin{align*} \mathrm{width}(\Phi^{\| \cdot \|_{1}}) = 2d, ~~ \mathrm{depth}(\Phi^{\| \cdot \|_{1}}) = 1, ~~ \Phi^{\| \cdot \|_{1}}({\boldsymbol{x}}) = \| {\boldsymbol{x}} \|_{1} \end{align*} \]

As a result, there exist ReLU neural networks \( \Phi_k:\mathbb{R}^d\to\mathbb{R}\) , \( k = 1, \dots, m\) , such that

\[ \begin{align*} \mathrm{width}(\Phi_k) = 2d, ~~ \mathrm{depth}(\Phi_k) = 1, ~~ \Phi_k({\boldsymbol{x}}) = y_k + M \| {\boldsymbol{x}} - {\boldsymbol{x}}_k \|_{1} \end{align*} \]

for all \( {\boldsymbol{x}} \in \mathbb{R}^d\) . Using the parallelization of neural networks introduced in Section 6.1.3, there exists a ReLU neural network \( \Phi_{\rm{all}}\mathrm{:}= (\Phi_1, \dots, \Phi_m)\colon \mathbb{R}^d \to \mathbb{R}^m\) such that

\[ \begin{align*} \mathrm{width}(\Phi_{\mathrm{all}} ) &= 4md, ~~ \mathrm{depth}(\Phi_{\mathrm{all}} ) = 1 \end{align*} \]

and

\[ \begin{align*} \Phi_{\mathrm{all}} ({\boldsymbol{x}}) &= (y_k + M \| {\boldsymbol{x}} - {\boldsymbol{x}}_k \|_{1})_{k=1}^m ~~ \text{ for all } {\boldsymbol{x}} \in \mathbb{R}^d. \end{align*} \]

Using Lemma 11, we can now find a ReLU neural network \( \Phi_{\mathrm{upper}}\) such that \( \Phi_{\mathrm{upper}} = f_{\mathrm{upper}}({\boldsymbol{x}})\) for all \( {\boldsymbol{x}} \in \Omega\) , \( \mathrm{width}(\Phi_{\mathrm{upper}}) \leq \max\{16 m, 4md\}\) , and \( \mathrm{depth}(\Phi_{\mathrm{upper}}) \leq 1 + \log(m)\) .

Essentially the same construction yields a ReLU neural network \( \Phi_{\mathrm{lower}}\) with the respective properties. Lemma 9 then completes the proof.

The universal interpolation theorem stated in this chapter is due to [1, Theorem 5.1]. There exist several earlier interpolation results, which were shown under stronger assumptions: In [4], the interpolation property is already linked with a rank condition on the matrix (104). However, no general conditions on the activation functions were formulated. In [5], the interpolation theorem is established under the assumption that the activation function \( \sigma\) is continuous and nondecreasing, \( \lim_{x \to -\infty} \sigma(x) = 0\) , and \( \lim_{x \to \infty} \sigma(x) = 1\) . This result was improved in [6], which dropped the nondecreasing assumption on \( \sigma\) .

The main idea of the optimal Lipschitz interpolation theorem in Section 10.2 is due to [2]. A neural network construction of Lipschitz interpolants, which however is not the optimal interpolant in the sense of Problem 1, is given in [7, Theorem 2.27].

The general idea of gradient descent is to start with some \( {\boldsymbol{w}}_0\in\mathbb{R}^n\) , and then apply sequential updates by moving in the direction of steepest descent of the objective function. Assume for the moment that \( f \in C^2(\mathbb{R}^n)\) , and denote the \( k\) th iterate by \( {\boldsymbol{w}}_k\) . Then

This shows that the change in \( f \) around \( {\boldsymbol{w}}_k\) is locally described by the gradient \( \nabla f ({\boldsymbol{w}}_k)\) . For small \( {\boldsymbol{v}}\) the contribution of the second order term is negligible, and the direction \( {\boldsymbol{v}}\) along which the decrease of the risk is maximized equals the negative gradient \( -\nabla f ({\boldsymbol{w}}_k)\) .

Thus, \( -\nabla f ({\boldsymbol{w}}_k)\) is also called the direction of steepest descent. This leads to an update of the form

where \( h_k>0\) is referred to as the step size or learning rate. We refer to this iterative algorithm as gradient descent.

By (109) and (110) it holds (also see [144, Section 1.2])

so that if \( \nabla f ({\boldsymbol{w}}_k)\neq\boldsymbol{0}\) , a small enough step size \( h_k\) ensures that the algorithm decreases the value of the objective function. In practice, tuning the learning rate \( h_k\) can be a subtle issue as it should strike a balance between the following dissenting requirements:

1. \( h_k\) needs to be sufficiently small so that the second-order term in (111) is not dominating, and the update (110) decreases the objective function.
2. \( h_k\) should be large enough to ensure significant decrease of the objective function, which facilitates faster convergence of the algorithm.

A learning rate that is too high might overshoot the minimum, while a rate that is too low results in slow convergence. Common strategies include, in particular, constant learning rates (\( h_k=h\) for all \( k\in\mathbb{N}_0\) ), learning rate schedules such as decaying learning rates (\( h_k\searrow 0\) as \( k\to\infty\) ), and adaptive methods. For adaptive methods the algorithm dynamically adjusts \( h_k\) based on the values of \( f ({\boldsymbol{w}}_j)\) or \( \nabla f ({\boldsymbol{w}}_j)\) for \( j\le k\) .

11.1.1 Structural conditions and existence of minimizers

We start our analysis by discussing three key notions for analyzing gradient descent algorithms, beginning with an intuitive (but loose) geometric description. A continuously differentiable objective function \( f :\mathbb{R}^n\to\mathbb{R}\) will be called

1. smooth if, at each \( {\boldsymbol{w}}\in\mathbb{R}^n\) , \( f \) is bounded above and below by a quadratic function that touches its graph at \( {\boldsymbol{w}}\) ,
2. convex if, at each \( {\boldsymbol{w}}\in\mathbb{R}^n\) , \( f \) lies above its tangent at \( {\boldsymbol{w}}\) ,
3. strongly convex if, at each \( {\boldsymbol{w}}\in\mathbb{R}^n\) , \( f \) lies above its tangent at \( {\boldsymbol{w}}\) plus a convex quadratic term.

These concepts are illustrated in Figure 33. We next give the precise mathematical definitions.

Definition 20

Let \( n\in \mathbb{N}\) and \( L>0\) . A function \( f :\mathbb{R}^n\to\mathbb{R}\) is called \( L\) -smooth if \( f \in C^1(\mathbb{R}^n)\) and

\[ \begin{align} f ({\boldsymbol{v}})&\le f ({\boldsymbol{w}})+\left\langle \nabla f ({\boldsymbol{w}}), {\boldsymbol{v}}-{\boldsymbol{w}}\right\rangle_{} + \frac{L}{2}\| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{}^2~~\text{for all }{\boldsymbol{w}},{\boldsymbol{v}}\in\mathbb{R}^n, \end{align} \]

(112.a)

\[ \begin{align} f ({\boldsymbol{v}})&\ge f ({\boldsymbol{w}})+\left\langle \nabla f ({\boldsymbol{w}}), {\boldsymbol{v}}-{\boldsymbol{w}}\right\rangle_{} - \frac{L}{2}\| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{}^2~~\text{for all }{\boldsymbol{w}},{\boldsymbol{v}}\in\mathbb{R}^n. \end{align} \]

(112.b)

By definition, \( L\) -smooth functions satisfy the geometric property (VII). In the literature, \( L\) -smoothness is often instead defined as Lipschitz continuity of the gradient

\[ \begin{align} \| \nabla f ({\boldsymbol{w}})-\nabla f ({\boldsymbol{v}}) \|_{} \le L \| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{}~~\text{for all }{\boldsymbol{w}},{\boldsymbol{v}}\in\mathbb{R}^n. \end{align} \]

(113)

Lemma 25

Let \( L>0\) . Then \( f \in C^1(\mathbb{R}^n)\) is \( L\) -smooth if and only if (113) holds.

Proof

We show that (112) implies (113). To this end assume first that \( f\in C^2(\mathbb{R}^n)\) , and that (113) does not hold. Then we can find \( {\boldsymbol{w}}\neq{\boldsymbol{v}}\) with

\[ \| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{} \sup_{\| {\boldsymbol{e}} \|_{}=1}\int_0^1 {\boldsymbol{e}}^\top\nabla^2 f ({\boldsymbol{v}}+t({\boldsymbol{w}}-{\boldsymbol{v}}))\frac{{\boldsymbol{w}}-{\boldsymbol{v}}}{\| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{}}\,\mathrm{d} t=\| \nabla f ({\boldsymbol{w}})-\nabla f ({\boldsymbol{v}}) \|_{} > L \| {\boldsymbol{w}}-{\boldsymbol{v}} \|_{}, \]

where \( \nabla^2 f \in\mathbb{R}^{n\times n}\) denotes the Hessian. Since the Hessian is symmetric, this implies existence of \( {\boldsymbol{u}}\) , \( {\boldsymbol{e}}\in\mathbb{R}^n\) with \( \| {\boldsymbol{e}} \|_{}=1\) and \( |{\boldsymbol{e}}^\top\nabla^2 f ({\boldsymbol{u}}){\boldsymbol{e}}|>L\) . Without loss of generality

\[ \begin{equation} {\boldsymbol{e}}^\top\nabla^2 f ({\boldsymbol{u}}){\boldsymbol{e}}>L. \end{equation} \]

(114)

Then for \( h>0\) by Taylor’s formula

\[ f ({\boldsymbol{u}}+h{\boldsymbol{e}}) = f ({\boldsymbol{u}}) + h\left\langle \nabla f ({\boldsymbol{u}}), {\boldsymbol{e}}\right\rangle_{} + \int_0^h {\boldsymbol{e}}^\top\nabla^2 f ({\boldsymbol{u}}+t{\boldsymbol{e}}){\boldsymbol{e}} (h-t)\,\mathrm{d} t. \]

Continuity of \( t\mapsto {\boldsymbol{e}}^\top\nabla^2 f ({\boldsymbol{u}}+t{\boldsymbol{e}}){\boldsymbol{e}}\) and (114) implies that for \( h>0\) small enough

\[ \begin{align*} f ({\boldsymbol{u}}+h{\boldsymbol{e}}) &> f ({\boldsymbol{u}}) + h\left\langle \nabla f ({\boldsymbol{u}}), {\boldsymbol{e}}\right\rangle_{} + L\int_0^h (h-t)\,\mathrm{d} t\\ &= f ({\boldsymbol{u}}) + \left\langle \nabla f ({\boldsymbol{u}}), h{\boldsymbol{e}}\right\rangle_{} + \frac{L}{2}\| h{\boldsymbol{e}} \|_{}^2. \end{align*} \]

This contradicts (112.a).

Now let \( f \in C^1(\mathbb{R}^n)\) and assume again that (113) does not hold. Then for every \( \varepsilon>0\) and every compact set \( K\subseteq\mathbb{R}^n\) there exists \( f_{\varepsilon,K}\in C^2(\mathbb{R}^n)\) such that \( \| f-f_{\varepsilon,K} \|_{C^1(K)}<\varepsilon\) . By choosing \( \varepsilon>0\) sufficiently small and \( K\) sufficiently large, it follows that \( f_{\varepsilon,K}\) violates (113). Consequently, by the previous argument, \( f_{\varepsilon,K}\) must also violate (112), which in turn implies that \( f\) does not satisfy (112) either.

Finally, the fact that (113) implies (112) is left as Exercise 34.

Definition 21

Let \( n \in \mathbb{N}\) . A function \( f :\mathbb{R}^n\to\mathbb{R}\) is called convex if and only if

\[ \begin{align} f (\lambda{\boldsymbol{w}}+(1-\lambda){\boldsymbol{v}}) \le \lambda f ({\boldsymbol{w}})+(1-\lambda) f ({\boldsymbol{v}}) \end{align} \]

(115)

for all \( {\boldsymbol{w}}\) , \( {\boldsymbol{v}}\in\mathbb{R}^n\) , \( \lambda\in (0,1)\) .

In case \( f \) is continuously differentiable, this is equivalent to the geometric property (VIII) as the next lemma shows. The proof is left as Exercise 35.

Lemma 26

Let \( f \in C^1(\mathbb{R}^n)\) . Then \( f \) is convex if and only if

\[ \begin{align} f ({\boldsymbol{v}})\ge f ({\boldsymbol{w}})+\left\langle \nabla f ({\boldsymbol{w}}), {\boldsymbol{v}}-{\boldsymbol{w}}\right\rangle_{} ~~ \text{for all }{\boldsymbol{w}},{\boldsymbol{v}}\in\mathbb{R}^n. \end{align} \]

(116)

The concept of convexity is strengthened by so-called strong-convexity, which requires an additional positive quadratic term on the right-hand side of (116), and thus corresponds to geometric property (IX) by definition.

Definition 22

Let \( n \in \mathbb{N}\) and \( \mu>0\) . A function \( f :\mathbb{R}^n\to\mathbb{R}\) is called \( \mu\) -strongly convex if \( f\in C^1(\mathbb{R}^n)\) and

\[ \begin{align} f ({\boldsymbol{v}}) \ge f ({\boldsymbol{w}})+\left\langle \nabla f ({\boldsymbol{w}}), {\boldsymbol{v}}-{\boldsymbol{w}}\right\rangle_{}+ \frac{\mu}{2}\| {\boldsymbol{v}}-{\boldsymbol{w}} \|_{}^2 ~~\text{for all }{\boldsymbol{w}},{\boldsymbol{v}}\in\mathbb{R}^n. \end{align} \]

(117)

A convex function need not be bounded from below (e.g\( w\mapsto w\) ) and thus need not have any (global) minimizers. And even if it is bounded from below, there need not exist minimizers (e.g\( w\mapsto \exp(w)\) ). However we have the following statement.

Lemma 27

Let \( f :\mathbb{R}^n\to\mathbb{R}\) . If \( f \) is

1. convex, then the set of minimizers of \( f \) is convex and has cardinality \( 0\) , \( 1\) , or \( \infty\) ,
2. \( \mu\) -strongly convex, then \( f \) has exactly one minimizer.

Proof

Let \( f \) be convex, and assume that \( {\boldsymbol{w}}_*\) and \( {\boldsymbol{v}}_*\) are two minimizers of \( f \) . Then every convex combination \( \lambda{\boldsymbol{w}}_*+(1-\lambda){\boldsymbol{v}}_*\) , \( \lambda\in [0,1]\) , is also a minimizer due to (115). This shows the first claim.

Now let \( f \) be \( \mu\) -strongly convex. Then (117) implies \( f \) to be lower bounded by a convex quadratic function. Hence there exists at least one minimizer \( {\boldsymbol{w}}_*\) , and \( \nabla f ({\boldsymbol{w}}_*)=0\) . By (117) we then have \( f ({\boldsymbol{v}})> f ({\boldsymbol{w}}_*)\) for every \( {\boldsymbol{v}}\neq{\boldsymbol{w}}_*\) .

11.1.2 Convergence of gradient descent

We next discuss a stochastic variant of gradient descent. The idea, which originally goes back to Robbins and Monro [149], is to replace the gradient \( \nabla f ({\boldsymbol{w}}_{k})\) in (110) by a random variable that we denote by \( {\boldsymbol{G}}_{k}\) . We interpret \( {\boldsymbol{G}}_k\) as an approximation to \( \nabla f ({\boldsymbol{w}}_{k})\) . More precisely, throughout we assume that given \( {\boldsymbol{w}}_{k}\) , \( {\boldsymbol{G}}_k\) is an unbiased estimator of \( \nabla f ({\boldsymbol{w}}_k)\) conditionally independent of \( {\boldsymbol{w}}_0,\dots,{\boldsymbol{w}}_{k-1}\) (see Appendix 18.3.3), so that

After choosing some initial value \( {\boldsymbol{w}}_0\in\mathbb{R}^n\) , the update rule becomes

where \( {h}_k>0\) denotes again the step size. Unlike in Section 11.1, we focus here on \( k\) -dependent step sizes \( h_k\) .

11.2.1 Motivation and decreasing learning rates

The next example motivates the algorithm in the standard setting, e.g[25, Chapter 8].

Example 5 (Empirical risk minimization)

Suppose we have a data sample \( S\mathrm{:}= ({\boldsymbol{x}}_j,y_j)_{j=1}^{m}\) , where \( y_j\in\mathbb{R}\) is the label corresponding to the data point \( {\boldsymbol{x}}_j\in\mathbb{R}^d\) . Using the square loss, we wish to fit a neural network \( \Phi(\cdot,{\boldsymbol{w}}):\mathbb{R}^d\to\mathbb{R}\) depending on parameters (i.eweights and biases) \( {\boldsymbol{w}}\in\mathbb{R}^n\) , such that the empirical risk in (3)

\[ \begin{align*} f ({\boldsymbol{w}})\mathrm{:}=\hat{\mathcal{R}}_S({\boldsymbol{w}})= \frac{1}{m}\sum_{j=1}^{{m}}(\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}})-y_j)^2, \end{align*} \]

is minimized. Performing one step of gradient descent requires the computation of

\[ \begin{align} \nabla f ({\boldsymbol{w}})=\frac{2}{m}\sum_{j=1}^{{m}}(\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}})-y_j)\nabla_{\boldsymbol{w}}\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}}), \end{align} \]

(123)

and thus the computation of \( {{m}}\) gradients of the neural network \( \Phi\) . For large \( {{m}}\) (in practice \( {{m}}\) can be in the millions or even larger), this computation might be infeasible.

To reduce computational cost, we replace the full gradient (123) by the stochastic gradient

\[ \begin{align*} {\boldsymbol{G}}\mathrm{:}= 2(\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}})-y_j)\nabla_{\boldsymbol{w}}\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}}) \end{align*} \]

where \( j\sim{\rm{uniform}}(1,\dots,{{m}})\) is a random variable with uniform distribution on the discrete set \( \{1,\dots,{{m}}\}\) . Then

\[ \begin{align*} \mathbb{E}[{\boldsymbol{G}}]=\frac{2}{m}\sum_{j=1}^{{m}}(\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}})-y_j)\nabla_{\boldsymbol{w}}\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}})=\nabla f ({\boldsymbol{w}}), \end{align*} \]

meaning that \( {\boldsymbol{G}}\) is an unbiased estimator of \( \nabla f ({\boldsymbol{w}})\) . Importantly, computing (a realization of) \( {\boldsymbol{G}}\) merely requires a single gradient evaluation of the neural network.

More generally, one can choose mini-batches In contrast to using the full batch, which corresponds to standard gradient descent. of size \( m_b\) (where \( m_b\ll {{m}}\) ) and let

\[ {\boldsymbol{G}}=\frac{2}{m_b}\sum_{j\in J}(\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}}) - y_j)\nabla_{\boldsymbol{w}}\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}}), \]

where \( J\) is a random subset of \( \{1,\dots,{{m}}\}\) of cardinality \( m_b\) . A larger mini-batch size reduces the variance of \( {\boldsymbol{G}}\) (thus giving a more robust estimate of the true gradient) but increases the computational cost.

A related common variant is the following: Let \( m_bk=m\) for \( m_b\) , \( k\) , \( m\in\mathbb{N}\) , i.ethe number of data points \( m\) is a \( k\) -fold multiple of the mini-batch size \( m_b\) . In each epoch, first a random partition \( \dot\bigcup_{i=1}^k J_i=\{1,\dots,m\}\) with \( |J_i|=m_b\) for each \( i\) , is determined. Then for each \( i=1,\dots,k\) , the weights are updated with the gradient estimate

\[ \begin{align*} \frac{2}{m_b}\sum_{j\in J_i}\Phi({\boldsymbol{x}}_j-y_j,{\boldsymbol{w}})\nabla_{\boldsymbol{w}}\Phi({\boldsymbol{x}}_j,{\boldsymbol{w}}). \end{align*} \]

Hence, in one epoch (corresponding to \( k\) updates of the weights), the algorithm sweeps through the whole dataset, and each data point is used exactly once.

Let \( {\boldsymbol{w}}_k\) be generated by (122). Using \( L\) -smoothness (113) we then have [150, Lemma 4.2]

\[ \begin{align*} \mathbb{E}[ f ({\boldsymbol{w}}_{k+1})|{\boldsymbol{w}}_k]- f ({\boldsymbol{w}}_{k}) &\le \mathbb{E}[\left\langle \nabla f ({\boldsymbol{w}}_k), {\boldsymbol{w}}_{k+1}-{\boldsymbol{w}}_k\right\rangle_{}] +\frac{L}{2}\mathbb{E}[\| {\boldsymbol{w}}_{k+1}-{\boldsymbol{w}}_k \|_{}^2|{\boldsymbol{w}}_k]\nonumber\\ &= -h_k \| \nabla f ({\boldsymbol{w}}_k) \|_{}^2 + \frac{L}{2}\mathbb{E}[\| h_k{\boldsymbol{G}}_k \|_{}^2|{\boldsymbol{w}}_k]. \end{align*} \]

For the objective function to decrease in expectation, the first term \( h_k\| \nabla f ({\boldsymbol{w}}_k) \|_{}^2\) should dominate the second term \( \frac{L}{2}\mathbb{E}[\| h_k{\boldsymbol{G}}_k \|_{}^2|{\boldsymbol{w}}_k]\) . As \( {\boldsymbol{w}}_k\) approaches the minimum, we have \( \| \nabla f ({\boldsymbol{w}}_k) \|_{}\to 0\) , which suggests that \( \mathbb{E}[\| h_k{\boldsymbol{G}}_k \|_{}^2|{\boldsymbol{w}}_k]\) should also decrease over time.

This is illustrated in Figure 34 (a), which shows the progression of stochastic gradient descent (SGD) with a constant learning rate, \( h_k = h\) , on a quadratic objective function and using artificially added gradient noise, such that \( \mathbb{E}[\| {\boldsymbol{G}}_k \|_{}^2|{\boldsymbol{w}}_k]\) does not tend to zero. The stochastic updates in (122) cause fluctuations in the optimization path. Since these fluctuations do not decrease as the algorithm approaches the minimum, the iterates will not converge. Instead they stabilize within a neighborhood of the minimum, and oscillate around it, e.g[148, Theorem 9.8]. In practice, this might yield a good enough approximation to \( {\boldsymbol{w}}_*\) . To achieve convergence in the limit, the variance of the update vector, \( -h_k {\boldsymbol{G}}_k\) , must decrease over time however. This can be achieved either by reducing the variance of \( {\boldsymbol{G}}_k\) , for example through larger mini-batches (cf. Example 5), or more commonly, by decreasing the step size \( h_k\) as \( k\) progresses. Figure 34 (b) shows this for \( h_k \sim 1/k\) ; also see Figure 37.

11.2.2 Convergence of stochastic gradient descent

Acceleration is an important tool for the training of neural networks [153]. The idea was first introduced by Polyak in 1964 under the name “heavy ball method” [154]. It is inspired by the dynamics of a heavy ball rolling down the valley of the loss landscape. Since then other types of acceleration have been proposed and analyzed, with Nesterov acceleration being the most prominent example [155]. In this section, we first give some intuition by discussing the heavy ball method for a simple quadratic loss. Afterwards we turn to Nesterov acceleration and give a convergence proof for \( L\) -smooth and \( \mu\) -strongly convex objective functions that improves upon the bounds obtained for gradient descent.

11.3.1 Heavy ball method