Optimal Approximation with Sparsely Connected Deep Neural Networks

Introduction

Neural networks arose from the seminal work by McCulloch and Pitts in 1943 which, inspired by the functionality of the human brain, introduced an algorithmic approach to learning with the aim of building a theory of artificial intelligence. Roughly speaking, a neural network consists of neurons arranged in layers and connected by weighted edges; in mathematical terms this boils down to a concatenation of affine linear functions and relatively simple non-linearities.

Despite significant theoretical progress in the 1990s , the area has seen practical progress only during the past decade, triggered by the drastic improvements in computing power and the availability of vast amounts of training data. Deep neural networks, i.e., networks with large numbers of layers, are now state-of-the-art technology for a wide variety of applications, such as image classification , speech recognition , or game intelligence . For an in-depth overview, we refer to the survey paper by LeCun, Bengio, and Hinton and the recent book .

A neural network effectively implements a non-linear mapping and can be used to either perform classification directly or to extract features that are then fed into a classifier, such as a support vector machine . In the former case, the primary goal is to approximate an unknown classification function based on a given set of input-output value pairs. This is typically accomplished by learning the network’s weights through, e.g., the stochastic gradient descent (via backpropagation) algorithm . In a classification task with, say, two classes, the function to be learned would take only two values, whereas in the case of, e.g., the prediction of the temperature in a certain environment, it would be real-valued. It is therefore clear that characterizing to what extent (deep) neural networks are capable of approximating general functions is a question of significant practical relevance.

Neural networks employed in practice often consist of hundreds of layers and may depend on billions of parameters, see for example the work on image classification. Training and operation of networks of this scale entail formidable computational challenges. As a case in point, we mention speech recognition on a smartphone such as, e.g., Apple’s SIRI-system, which operates in the cloud. Android’s speech recognition system has meanwhile released an offline version based on a neural network with sparse connectivity. The desire to reduce the complexity of network training and operation naturally leads to the question of the fundamental limits on function approximation through neural networks with sparse connectivity. In addition, the network’s memory requirements in terms of the number of bits needed to store its topology and weights are of concern in practice.

The purpose of this paper is to understand the connectivity and memory requirements of (deep) neural networks induced by demands on their approximation-theoretic properties. Specifically, defining the complexity of a function class $\mathcal{C}$ as the rate of growth of the minimum number of bits needed to describe any element in $\mathcal{C}$ to within a maximum allowed error approaching zero, we shall be interested in the following question: Depending on the complexity of $\mathcal{C}$, what are the connectivity and memory requirements of a deep neural network approximating every element in $\mathcal{C}$ to within an error of $\varepsilon$? We address this question by interpreting the network as an encoder in Donoho’s min-max rate distortion theory and establishing rate-distortion optimality for a broad family of function classes $\mathcal{C}$, namely those classes for which so-called affine systems—a general class of representation systems—yield optimal approximation rates in the sense of non-linear approximation theory . Affine systems encompass a wealth of representation systems from applied harmonic analysis such as wavelets , ridgelets , curvelets , shearlets , $\alpha$-shearlets and more generally $\alpha$-molecules . Our result therefore uncovers an interesting universality property of deep neural networks; they exhibit the optimal approximation properties of all affine systems combined. The technique we develop to prove our main statements is interesting in its own right as it constitutes a more general framework for transferring results on function approximation through representation systems to results on approximation by deep neural networks.

While various network architectures exist in the literature, we focus on the following setup.

The term “network” stems from the interpretation of the mapping $\Phi$ as a weighted acyclic directed graph with nodes arranged in $L+1$ hierarchical layers and edges only between adjacent layers. If the network’s connectivity $\mathcal{M}(\Phi)$ is small relative to the number of connections possible (i.e., the number of edges in the graph that is fully connected between adjacent layers), we say that the network is sparsely connected.

2 Quantifying Approximation Quality

We proceed to formalizing our problem statement and start with a brief review of a widely used framework in approximation theory .

We call $\Gamma_{M}^{\mathcal{D}}(f)$ the best $M$-term approximation error of $f$ in $\mathcal{D}$. Every $f_{M}=\sum_{i\in I_{M}}c_{i}\varphi_{i}$ attaining the infimum in (2) is referred to as a best $M$-term approximation of $f$ in $\mathcal{D}$. The supremal $\gamma>0$ such that

will be denoted by $\gamma^{\ast}(\mathcal{C},\mathcal{D})$. We say that the best $M$-term approximation rate of $\mathcal{C}$ in the representation system $\mathcal{D}$ is $\gamma^{\ast}(\mathcal{C},\mathcal{D})$.

Function classes $\mathcal{C}$ widely studied in the approximation theory literature include unit balls in Lebesgue, Sobolev, or Besov spaces , as well as $\alpha$-cartoon-like functions . A wealth of structured representation systems $\mathcal{D}$ is provided by the area of applied harmonic analysis, starting with wavelets , followed by ridgelets , curvelets , shearlets , parabolic molecules , and most generally $\alpha$-molecules , which include all previously named systems as special cases. Further examples are Gabor frames and wave atoms .

3 Approximation by Deep Neural Networks

The main conceptual contribution of this paper is the development of an approximation-theoretic framework for deep neural networks in the spirit of . Specifically, we shall substitute the concept of best $M$-term approximation with representation systems by best $M$-edge approximation through neural networks. In other words, parsimony in terms of the number of participating elements of a representation system is replaced by parsimony in terms of connectivity. More formally, we consider the following setup.

We call $\Gamma_{M}^{\mathcal{N}\mathcal{N}}(f)$ the best $M$-edge approximation error of $f$. The supremal $\gamma>0$ such that

will be denoted by $\gamma_{\mathcal{N}\mathcal{N}}^{\ast}(\mathcal{C},\rho)$. We say that the best $M$-edge approximation rate of $\mathcal{C}$ by neural networks with activation function $\rho$ is $\gamma_{\mathcal{N}\mathcal{N}}^{\ast}(\mathcal{C},\rho)$.

We emphasize that the infimum in (3) is taken over all networks with fixed activation function $\rho$, fixed input dimension $d$, no more than $M$ edges of nonzero weight, and arbitrary number of layers $L$. In particular, this means that the infimum is taken over all possible network topologies. The resulting best $M$-edge approximation rate is fundamental as it benchmarks all learning algorithms, i.e., all algorithms that map an input function $f$ and an $\varepsilon>0$ to a neural network that approximates $f$ with error no more than $\varepsilon$. Our framework hence provides a means for assessing the performance of a given learning algorithm in the sense of allowing to measure how close the $M$-edge approximation rate induced by the algorithm is to the best $M$-edge approximation rate $\gamma_{\mathcal{N}\mathcal{N}}^{\ast}(\mathcal{C},\rho)$.

4 Previous Work

The best-known results on approximation by neural networks are the universal approximation theorems of Hornik and Cybenko , stating that every measurable function $f$ can be approximated arbitrarily well by a single-hidden-layer ($L=2$ in our terminology) neural network. The literature on approximation-theoretic properties of networks with a single hidden layer continuing this line of work is abundant. Without any claim to completeness, we mention work on approximation error bounds in terms of the number of neurons for functions with bounded first moments , , the non-existence of localized approximations , a fundamental lower bound on approximation rates , and the approximation of smooth or analytic functions .

Approximation-theoretic results for networks with multiple hidden layers were obtained in for general functions, in for continuous functions, and for functions together with their derivatives in . In it was shown that for certain approximation tasks deep networks can perform fundamentally better than single-hidden-layer networks. We also highlight two recent papers, which investigate the benefit—from an approximation-theoretic perspective—of multiple hidden layers. Specifically, in it was shown that there exists a function which, although expressible through a small three-layer network, can only be represented through a very large two-layer network; here size is measured in terms of the total number of neurons in the network. In the setting of deep convolutional neural networks, first results of a nature similar to those in were reported in . Additionally, by linking the expressivity properties of neural networks to tensor decompositions, established the existence of functions that can be realized by relatively small deep convolutional networks but require exponentially larger shallow networks. For survey articles on approximation-theoretic aspects of neural networks, we refer the interested reader to .

Most closely related to our work is that by Shaham, Cloninger, and Coifman , which shows that for functions that are sparse in specific wavelet frames, the best $M$-edge approximation rate of three-layer neural networks is at least as high as the best $M$-term approximation rate in piecewise linear wavelet frames.

5 Contributions

Our contributions can be grouped into four threads.

Fundamental lower bound on connectivity. We quantify the minimum network connectivity needed to allow approximation of all elements of a given function class $\mathcal{C}$ to within a maximum allowed error. On a conceptual level, this result establishes a universal link between the complexity of a given function class and the connectivity required by corresponding approximating neural networks.

Transfer from $M$-term to $M$-edge approximation. We develop a general framework for transferring best $M$-term approximation results in representation systems to best $M$-edge approximation results for neural networks.

Memory requirements. We characterize the memory requirements needed to store the topology and the quantized weights of optimally-approximating neural networks.

Realizability of optimal approximation rates. An important practical question is how neural networks trained by stochastic gradient descent (via backpropagation) perform relative to the fundamental bounds established in the paper. Interestingly, our numerical experiments indicate that stochastic gradient descent can achieve $M$-edge approximation rates quite close to the fundamental limit.

6 Outline of the Paper

Section 2 introduces the novel concept of effective best $M$-edge approximation. The fundamental lower bound on connectivity is developed in Section 3. Section 4 describes a general framework for transferring best $M$-term approximation results in representation systems to best $M$-edge approximation results for neural networks. In Section 5, we apply this transfer framework to the broad class of affine representation systems, and Section 6 shows that this leads to optimal $M$-edge approximation rates for cartoon functions. In Section 7, we briefly outline the extension of our main findings to the approximation of functions defined on manifolds. Finally, numerical results assessing the performance of stochastic gradient descent (via backpropagation) relative to our lower bound on connectivity are reported in Section 8.

Effective Best M𝑀M-term and Best M𝑀M-edge Approximation

We proceed by introducing $M$-term approximation via dictionaries and $M$-edge approximation via neural networks. These concepts do, however, not allow for a meaningful notion of optimality in practice. A remedy is provided by effective best $M$-term approximation according to and the new concept of effective best $M$-edge approximation introduced below.

will be denoted by $\gamma^{\ast,\text{eff}}(\mathcal{C},\mathcal{D})$ and referred to as effective best $M$-term approximation rate of $\mathcal{C}$ in the representation system $\mathcal{D}$.

We will demonstrate in Section 3.2 that $\sup_{\mathcal{D}\subset L^{2}(\Omega)}\gamma^{\ast,\text{eff}}(\mathcal{C},\mathcal{D})$ is, indeed, finite under quite general conditions on $\mathcal{C}$ and, in particular, depends on the “description complexity” of $\mathcal{C}$. This will allow us to assess the approximation capacity of a given representation system $\mathcal{D}$ for $\mathcal{C}$ by comparing $\gamma^{\ast,\text{eff}}(\mathcal{C},\mathcal{D})$ to the ultimate limit $\sup_{\mathcal{D}\subset L^{2}(\Omega)}\gamma^{\ast,\text{eff}}(\mathcal{C},\mathcal{D})$.

2 Effective Best M𝑀M-edge Approximation

Now, as $\varepsilon$ in Theorem 2.2 can be made arbitrarily small while the connectivity of the corresponding networks remains upper-bounded by $21d^{2}+15d+3$, (6) would have to hold for arbitrarily large $\gamma$, in particular also for $\gamma>\gamma_{\mathcal{N}\mathcal{N}}^{\ast,\text{eff}}(\mathcal{C},\rho)$, where $\gamma_{\mathcal{N}\mathcal{N}}^{\ast,\text{eff}}(\mathcal{C},\rho)$ is the effective best $M$-edge approximation rate according to Definition 2.3. By Theorem 3.4 below, however, $\gamma_{\mathcal{N}\mathcal{N}}^{\ast,\text{eff}}(\mathcal{C},\rho)\leq{\gamma^{\ast}(\mathcal{C})}$, where ${\gamma^{\ast}(\mathcal{C})}$ is the optimal exponent according to Definition 3.1. Owing to Definition 2.3, we can therefore conclude that the weights of the network achieving the infimum in (6) can not be bounded by a polynomial in $M\sim\varepsilon^{-1}$ whenever $\gamma^{\ast}(\mathcal{C})<\infty$. Here and in the sequel, we write $a\sim b$ if the variables $a$ and $b$ are proportional, i.e., there exist uniform constants $c_{1},c_{2}>0$ such that $c_{1}a\leq b\leq c_{2}a$.

The observation just made resembles the problem in best $M$-term approximation which eventually led to the concept of effective best $M$-term approximation, where we restricted the search depth in the representation system $\mathcal{D}$ to be bounded by a given polynomial in $M$ and the coefficients $c_{i}$ to be bounded according to $\max_{i\in I_{M}}\!|c_{i}|\,\leq\,D$. Interpreting the weights in the network as the counterpart of the coefficients $c_{i}$ in best $M$-term approximation, we see that the restriction on the search depth corresponds to restricting the size of the indices enumerating the participating weights. The need for such a restriction is obviated by the tree structure of deep neural networks as exposed in detail in the proof of Proposition 3.6. The second restriction will lead us to a growth condition on the weights, which is more generous than the corresponding requirement of the $c_{i}$ in effective best $M$-term approximation being bounded.

In summary, this leads to the novel concept of “best $M$-edge approximation subject to polynomial weight growth” as formalized next.

where ${\mathcal{N}\mathcal{N}}_{L,M,d,\rho}^{\pi}$ denotes the class of networks in ${\mathcal{N}\mathcal{N}}_{L,M,d,\rho}$ that have all their weights bounded in absolute value by $\pi(M)$, will be referred to as effective best $M$-edge approximation rate of $\mathcal{C}$ by neural networks and denoted by $\gamma^{\ast,\text{eff}}_{\mathcal{N}\mathcal{N}}(\mathcal{C},\rho)$.

Fundamental Bounds on Effective M𝑀M-Term and M𝑀M-Edge Approximation Rate

The purpose of this section is to establish fundamental bounds on effective best $M$-term and effective best $M$-edge approximation rates by evaluating the corresponding approximation strategies in the min-max rate distortion theory framework as developed in .

Min-max rate distortion theory provides a theoretical foundation for deterministic lossy data compression. We recall the following notions and concepts from .

Moreover, the optimal exponent $\gamma^{*}(\mathcal{C})$ is defined as

The optimal exponent $\gamma^{*}(\mathcal{C})$ quantifies the minimum growth rate of $L(\varepsilon,\mathcal{C})$ as the error $\varepsilon$ tends to zero and can hence be seen as quantifying the “description complexity” of the function class $\mathcal{C}$. Larger $\gamma^{*}(\mathcal{C})$ results in smaller growth rate and hence smaller memory requirements for storing signals $f\in\mathcal{C}$ such that reconstruction with uniformly bounded error is possible. The quantity $\gamma^{*}(\mathcal{C})$ is closely related to the concept of Kolmogorov entropy . Remark 5.10 in makes this connection explicit.

2 Fundamental Bound on Effective Best M𝑀M-Term Approximation Rate

We next recall a result from , which says that, for a given function class $\mathcal{C}$, the optimal exponent $\gamma^{*}(\mathcal{C})$ constitutes a fundamental bound on the effective best $M$-term approximation rate of $\mathcal{C}$ in any representation system. This gives operational meaning to $\gamma^{*}(\mathcal{C})$.

In light of this result the following definition is natural (see also ).

then the function class $\mathcal{C}$ is said to be optimally representable by $\mathcal{D}$.

3 Fundamental Bound on Effective Best M𝑀M-Edge Approximation Rate

The key ingredients of the proof of Theorem 3.4 are developed throughout this section and the formal proof will be stated at the end of the section. Before embarking on this, we note that, in analogy to Definition 3.3, what we just found suggests the following.

It is remarkable that the fundamental limits of approximation through representation systems and approximation through deep neural networks are determined by the same quantity, although the approximants in the two cases are vastly different, namely linear combinations of elements of a representation system with the participating functions identified subject to a polynomial-depth search constraint in the former, and concatenations of affine functions followed by non-linearities under growth constraints on the weights in the network in the latter case.

A key ingredient of the proof of Theorem 3.4 is the following result, which establishes a fundamental lower bound on the connectivity of networks with quantized weights achieving uniform error $\varepsilon$ over a given function class.

We recall that the number of layers of $\Phi$ is denoted by $L$, the number of nodes in these layers is $N_{1},\dots,N_{L}$ (see Definition 1.1), and $d$ stands for the dimension of the input layer.

where we let $\widetilde{M}:=M+d$. All other nodes do not contribute to the mapping $\Phi(x)$ and can hence be ignored.

realizes the same function as the original network $\Phi$ but has less than $L$ layers. This reduction can be repeated inductively until the resulting reduced network satisfies (12).

The bitstring representing $\Phi$ is constructed according to the following steps.

Step 1: If $M=0$, we encode the network by a leading followed by the bitstring representing the node weight in the last layer. Upon defining $0\log_{2}(0)=0$, we then note that (10) holds trivially and we terminate the encoding procedure. Else, we encode the number of nonzero edge weights, $M$, by starting the overall bitstring with $M$ $1$’s followed by a single . The length of this bitstring is therefore bounded by $\widetilde{M}$.

Step 2: We continue by encoding the number of layers in the network. Thanks to (12) this requires no more than $\log_{2}(\widetilde{M})$ bits. We thus reserve the next $\log_{2}(\widetilde{M})$ bits for the binary representation of $L$.

In combination with Steps 1 and 2 this yields an overall bitstring of length at most

where we used $\sum_{i=1}^{\widetilde{N}}n(i)=M<\widetilde{M}$ and (11). Combining (13) and (14) it follows that we have encoded the overall topology of the network $\Phi$ using at most

Step 5: We encode the weights of $\Phi$. By assumption, each weight can be represented by a bitstring of length $\lceil c\log_{2}(\varepsilon^{-1})\rceil$. For each node $i=1,\dots,\widetilde{N}$, we reserve the first $\lceil c\log_{2}(\varepsilon^{-1})\rceil$ bits to encode its associated node weight and, for each of its children a bitstring of length $\lceil c\log_{2}(\varepsilon^{-1})\rceil$ to encode the weight corresponding to the edge between that child and its parent node. Concatenating the results in ascending order of child node indices, we get a bitstring of length $(n(i)+1)\cdot(\lceil c\log_{2}(\varepsilon^{-1})\rceil)$ for node $i$, and an overall bitstring of length

representing the weights of the graph associated with the network $\Phi$.

With (15) this shows that the overall number of bits needed to encode the network topology and weights is no more than

Proposition 3.6 applies to networks that have each weight represented by a finite number of bits scaling according to $\log_{2}(\varepsilon^{-1})$ while guaranteeing that the underlying encoder-decoder pair achieves uniform error $\varepsilon$ over $\mathcal{C}$. We next show that such a compatibility is possible for networks with activation functions that are either Lipschitz or differentiable such that $\rho^{\prime}$ is dominated by an arbitrary polynomial. We can now demonstrate that for sufficiently regular activation functions, faithful quantization of the weights of a network is possible.

We prove the statement for Lipschitz-continuous $\rho$ only. The argument for differentiable activation functions with first derivative not growing faster than every polynomial is along similar lines.

Denote the maximum of 1 and the Lipschitz constant of $\rho$ by $C_{\rho}$, set $C_{0}:=\max\{1,\sup\{|x|:x\in\Omega\}\}$, and let

Using (21) and (23) in (20), we finally obtain

which yields $e_{L}\leq\eta$ for sufficiently large $m$. ∎

We will refrain from explicitly specifying the $D_{i}$ in Definition 3.9 whenever they are clear from the context.

Setting $M_{\varepsilon}:=\lceil(\varepsilon/(3C))^{-1/\gamma}\rceil$, it follows that, for every $f\in\mathcal{C}$ and every $\varepsilon\in(0,1/2)$, there exists a neural network $\Phi_{\varepsilon,f}\in{\mathcal{N}\mathcal{N}}_{L,M_{\varepsilon},d,\rho}^{\pi}$ such that

As the weights of $\Phi_{\varepsilon,f}$ are polynomially bounded in $M_{\varepsilon}$, they are polynomially bounded in $\varepsilon^{-1}$. By Lemma 3.7 and Remark 3.10, there hence exists a network $\widetilde{\Phi}_{\varepsilon,f}$ whose weights are represented by no more than $\lceil c\log_{2}(\varepsilon^{-1})\rceil$ bits, for some constant $c>0$, satisfying

The proof is concluded by noting that Learn violates Proposition 3.6. ∎

We can now proceed to the proof of Theorem 3.4.

This, however, constitutes a contradiction to Proposition 3.11. ∎

We conclude this section with a discussion of the conceptual implications of the results established above. Proposition 3.6 combined with Lemma 3.7 establishes that neural networks with weights polynomially bounded in $\varepsilon^{-1}$ and achieving uniform approximation error $\varepsilon$ over $\mathcal{C}$ cannot exhibit edge growth rate smaller than $\mathcal{O}(\varepsilon^{-1/\gamma^{*}(\mathcal{C})}),\varepsilon\rightarrow 0$; in other words, a decay of the uniform approximation error, as a function of $M$, faster than $\mathcal{O}(M^{-\gamma^{\ast}(\mathcal{C})}),M\rightarrow\infty$, is not possible.

Note that requiring uniform approximation error $\varepsilon$ only (without imposing the constraint of the network’s weights being polynomially bounded in $\varepsilon^{-1}$) can lead to arbitrarily large rate $\gamma$ as exemplified by Theorem 2.2, which proves the existence of networks realizing an arbitrarily small approximation error over $L^{2}(^{d})$ with a finite number of nodes; in particular, the number of nodes remains constant as $\varepsilon\rightarrow 0$. However, as argued right after Theorem 2.2, these networks necessarily lead to weights that are not polynomially bounded in $\varepsilon^{-1}$.

Transitioning from Representation Systems to Neural Networks

The remainder of this paper is devoted to identifying function classes that are optimally representable—according to Definition 3.5—by neural networks. The mathematical technique we develop in the process is interesting in its own right as it constitutes a general framework for transferring results on function approximation through representation systems to results on approximation by neural networks. In particular, we prove that for a given function class $\mathcal{C}$ and an associated representation system $\mathcal{D}$ which satisfies certain technical conditions, there exists a neural network with $\mathcal{O}(M)$ nonzero edge weights that achieves (up to a multiplicative constant) the same uniform error over $\mathcal{C}$ as a best $M$-term approximation in $\mathcal{D}$. This will finally lead to a characterization of function classes $\mathcal{C}$ that are optimally representable by neural networks in the sense of Definition 3.5.

We start by stating technical conditions on representation systems for the transference principle outlined above to apply.

If, in addition, the weights of $\Phi_{i,\eta}\in\mathcal{N}\mathcal{N}_{L,R,d,\rho}$ are polynomially bounded in $i,\eta^{-1}$, and if $\rho$ is either Lipschitz-continuous or differentiable such that $\rho^{\prime}$ is dominated by an arbitrary polynomial, then we say that $\mathcal{D}$ is effectively representable by neural networks (with activation function $\rho$).

In particular, for all function classes $\mathcal{C}\subset L^{2}(\Omega)$ it holds that

Let then $\Phi(f,M)$ be the neural network consisting of the networks $(\Phi_{i,\eta})_{i\in I_{M}}$ operating in parallel, all with the same input, and summing their one-dimensional outputs (see Figure 3 below for an illustration) with weights $(c_{i})_{i\in I_{M}}$ according to

This construction is legitimate as all networks $\Phi_{i,\eta}$ have the same number of layers and the last layer of a neural network according to Definition 1.1 implements an affine function only (without subsequent application of the activation function $\rho$). Then, $\Phi(f,M)\in\mathcal{N}\mathcal{N}_{L,RM,d,\rho}$, and application of the triangle inequality together with (27) yields $\left\|f_{M}-\Phi(f,M)\right\|_{L^{2}(\Omega)}\leq\varepsilon$. Another application of the triangle inequality according to

finalizes the proof of (25) which by Definitions 1.2 and 1.3 implies (26). ∎

Theorem 4.2 shows that we can restrict ourselves to the approximation of the individual elements of a representation system by neural networks with the only constraint being that the number of nonzero edge weights in the individual networks must admit a uniform upper bound. Theorem 4.2 does, however, not guarantee that the weights of the network $\Phi(f,M)$ can be represented with no more than $\lceil c\log_{2}(\varepsilon^{-1})\rceil$ bits when the overall approximation error is proportional to $\varepsilon$. This will again be accomplished through a transfer argument, applied to representation systems $\mathcal{D}$ satisfying slightly more stringent technical conditions.

Theorem 4.3 implies that if $\mathcal{D}$ optimally represents the function class $\mathcal{C}$ in the sense of Definition 3.3 and at the same time is effectively representable by neural networks, then $\mathcal{C}$ is optimally representable by neural networks in the sense of Definition 3.5.

In addition, the weights of $\Phi_{i,\eta}$ are polynomially bounded in $i,\eta^{-1}$. Let then $\Phi(f,M)\in\mathcal{N}\mathcal{N}_{L,RM,d,\rho}$ be the neural network consisting of the networks $(\Phi_{i,\eta})_{i\in I_{M}}$ operating in parallel, according to (28). We conclude that

As the weights of the networks $\Phi_{i,\eta}$ are polynomially bounded in $i,\eta^{-1}$ and $i\leq\pi(M),\delta_{M}\sim M^{-\gamma}$, it follows that the weights of $\Phi(f,M)$ are polynomially bounded in $\delta_{M}^{-1}$.

and all weights of $\widetilde{\Phi}(f,M)$ can be represented with no more than $\lceil c\log_{2}(\delta_{M}^{-1})\rceil$ bits, for some $c>0$. Moreover, we have

With this choice of $M_{\varepsilon}$, we have $CM_{\varepsilon}^{-\gamma}\leq\varepsilon$, which, when used in (30), yields

All Affine Representation Systems are Effectively Representable by Neural Networks

This section shows that a large class of representation systems, namely affine systems, defined below, are effectively representable by neural networks. Affine systems include as special cases wavelets, ridgelets, curvelets, shearlets, $\alpha$-shearlets, and more generally $\alpha$-molecules. Combined with Theorem 4.3 the results in this section establish that any function class that is optimally represented by an arbitrary affine system is optimally represented by neural networks in the sense of Definition 3.5.

Clearly, such strong statements are possible only under restrictions on the choice of the activation function for the approximating neural networks.

We consider two classes of activation functions, namely sigmoidal functions and smooth approximations of rectified linear units. We start with the formal definition of sigmoidal activation functions as considered in .

A differentiable function $\rho$ is called strongly sigmoidal of order $k$, if there exist constants $a,b,C>0$ such that

One of the most widely used activation functions is the so-called rectified linear unit (ReLU) given by $x\mapsto\max\{0,x\}$. The second class of activation functions we consider here are smooth versions of the ReLU.

for some constant $K>0$. Then, we call $\rho$ an admissible smooth activation function.

The reason for considering these two specific classes of activation functions resides in the fact that neural networks based thereon allow economical representations of multivariate bump functions, which, in turn, leads to effective representation of all affine systems (built from bump functions) by neural networks. Approximation of multivariate bump functions using sparsely connected neural networks is a classical topic in neural network theory . What is new here is the aspect of quantized weights and rate-distortion optimality.

Additionally, we will need to control the weights in the approximating networks $\Phi_{D,\varepsilon}$. We next show that this is, indeed, possible for strongly sigmoidal activation functions.

Moreover, the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$.

The neural network $\Phi_{D,\varepsilon}$ in Theorem 5.3 is explicitly constructed in . Carefully following the steps in that construction and making explicit use of the strong sigmoidality of $\rho$, as opposed to plain sigmoidality as in , yields the desired result. ∎

We observe that the number of edges of the approximating network in Theorem 5.4 does not depend on the approximation error $\varepsilon$.

$\widehat{\Phi}_{\rho}(\xi)\neq 0$, for all $\xi\in^{d}$.

By construction, $g\in C^{\infty}$ is compactly supported. Moreover, $g$ can be realized through a three-layer neural network thanks to its two-step design per (33) and (34). Since $g\geq 0$ and $g\neq 0$, it follows that $|\hat{g}(0)|>0$. By continuity of $\hat{g}$ there exists a $\delta>0$ such that $|\hat{g}(\xi)|>0$ for all $\xi\in[-\delta,\delta]^{d}$. We now set

2 Invariance to Affine Transformations

We next leverage Theorems 5.4 and 5.6 to demonstrate that a wide class of representation systems built through affine transformations of $B$-splines and bump functions as constructed in Theorem 5.6 is effectively representable by neural networks. As a first step towards this general result, we show that representability—in the sense of Definition 4.1—of a single function $f$ by neural networks is invariant to the operation of taking finite linear combinations of affine transformations of $f$.

Moreover, if the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$, then the weights of $\Psi_{E,\eta}$ are polynomially bounded in $\|A\|_{\infty},E,\|b\|_{\infty},\eta^{-1}$, where $\|A\|_{\infty}$ and $\|b\|_{\infty}$ denote the max-norm of $A$ and $b$, respectively.

By a change of variables, we have for every $\Phi\in\mathcal{N}\mathcal{N}_{L,M,d,\rho}$ that

and there exists $M^{\prime}$ depending on $M$ and $d$ only such that $|\!\det(A)|^{1/2}\Phi(A\cdot-\,b)\in\mathcal{N}\mathcal{N}_{L,M^{\prime},d,\rho}$. We furthermore have that

We now set $F=dE\|A\|_{\infty}+\|b\|_{\infty}$ and $\Psi_{E,\eta}:=|\!\det(A)|^{1/2}\Phi_{F,\eta}(A\cdot-\,b)$ and observe that

where we applied the same reasoning as in (36) in the first equality, (37) in the first inequality, and (35) in the second inequality. Moreover, we see that if the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$, then the weights of $\Psi_{E,\eta}$ are polynomially bounded in $\|A\|_{\infty},|\!\det(A)|,E,\|b\|_{\infty},\eta^{-1}$. Since $|\!\det(A)|$ is polynomially bounded in $\|A\|_{\infty}$, it follows that the weights of $\Psi_{E,\eta}$ are polynomially bounded in $|\|A\|_{\infty},E,\|b\|_{\infty},\eta^{-1}$. This yields the claim. ∎

Next, we show that representability by neural networks is preserved under finite linear combinations of translates.

Moreover, if the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$, then the weights of $\Psi_{E,\eta}$ are polynomially bounded in

Let $E,\eta>0$. We start by noting that, for all $D,\varepsilon>0$,

where $d^{*}=\max_{i=1,\dots,r}\|d_{i}\|_{\infty}$. Setting $D=E+d^{*}$ and $\varepsilon=\eta/\max\{1,\sum_{i=1}^{r}|c_{i}|\}$, and noting that for every $\Phi\in\mathcal{N}\mathcal{N}_{L,M,d,\rho}$, the function

satisfies (39). Finally, if the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$, then the weights of $\Psi_{E,\eta}$ are polynomially bounded in $\sum_{i=1}^{r}|c_{i}|,E,d^{*},\eta^{-1}$.

Based on the invariance results in Propositions 5.7 and 5.8, we now construct neural networks which approximate functions with a given number of vanishing moments with arbitrary accuracy. The resulting construction will be crucial in establishing representability of affine representation systems (see Definition 5.11) by neural networks.

The next result establishes that functions with an arbitrary number of vanishing moments in a given coordinate direction can be built from suitable linear combinations of translates of a given continuous function with compact support.

has $R$ directional vanishing moments in $x_{k}$-direction. Moreover, if $\hat{f}(\xi)\neq 0$ for all $\xi\in[-B,B]^{d}\setminus\{0\}$, then

For simplicity of exposition, we consider the case $B=1$ only. Taking the Fourier transform of (40) yields

But by Definition 5.9, this says precisely that $g$ possesses the desired vanishing moments. Statement (41) follows by inspection of (42). ∎

3 Affine Representation Systems

We are now ready to introduce the general family of representation systems announced earlier in the paper as affine systems. This class includes all representation systems based on affine transformations of a given “mother function”. Special cases of affine systems are wavelets, ridgelets, curvelets, shearlets, $\alpha$-shearlets, and more generally $\alpha$-molecules, as well as tensor products thereof. The formal definition of affine systems is as follows.

We define the affine system $\mathcal{D}\subset L^{2}(\Omega)$ corresponding to $(g_{s})_{s=1}^{S}$ according to

and refer to $f$ as the generator function of $\mathcal{D}$.

As the $\mathcal{D}_{s,j}$ are finite, we can organize the representation system $\mathcal{D}$ according to

where the elements within each sub-system $\mathcal{D}_{s,j}$ may be ordered arbitrarily. This ordering of $\mathcal{D}$ is assumed in the remainder of the paper and will be referred to as canonical ordering.

Moreover, we note that if there exists $s_{o}\in\{1,\dots,S\}$ such that $g_{s_{o}}$ is nonzero, then there is a constant $c_{\textrm{o}}:=c_{\textrm{o}}((g_{s})_{s=1}^{S},\delta,d)>0$ such that

The next result establishes that all affine systems whose generator functions can be approximated to within arbitrary accuracy by neural networks are (effectively) representable by neural networks.

Then, $\mathcal{D}$ is representable by neural networks with activation function $\rho$. If, in addition, the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$, and if there exist $a>0$ and $c>0$ such that

then $\mathcal{D}$ is effectively representable by neural networks with activation function $\rho$.

Let $(g_{s})_{s=1}^{S}$ be as in Definition 5.11. If $g_{s}=0$ for all $s\in\{1,\dots,S\}$, then $\mathcal{D}={{\varnothing}}$ and the result is trivial. Hence, we can assume that there exists at least one $s\in\{1,\dots,S\}$ such that $g_{s}\neq 0$, implying that (45) holds.

The elements of $\mathcal{D}$ consist of dilations and translations of $f$ according to

It remains to show that the weights of $\Phi_{D,\varepsilon}$ in (46) polynomially bounded in $D,\varepsilon^{-1}$ implies that $\mathcal{D}$ is effectively representable by neural networks with activation function $\rho$, which, by Definition 4.1, means that the weights of $\Phi_{i,\eta}$ are polynomially bounded in $i,\eta^{-1}$. Propositions 5.7 and 5.8 state that the weights of $\Phi_{i,\eta}$ are polynomially bounded in

Thanks to (43) we have $\|b_{i}\|_{\infty}\in\mathcal{O}(\|A_{j_{i}}\|_{\infty})$. Moreover, the quantities $D$, $\sum_{k=1}^{r}|c_{k}|$, and $\max_{k=1,\dots,r}\|d_{k}\|_{\infty}$ do not depend on $i$. We can thus conclude that the weights of $\Phi_{i,\eta}$ are polynomially bounded in

To complete the proof, we need to show that the quantities $\|A_{j_{i}}\|_{\infty}$ are polynomially bounded in $i$. To this end, we first observe that $\varphi_{i}$ according to (49) satisfies $\varphi_{i}\in\mathcal{D}_{s_{i},j_{i}}$ for some $s_{i}\in\{1,\dots,S\}$. Thanks to (45) and the canonical ordering (44), there exists a constant $c>0$ such that

We finally appeal to (47) to conclude that $\|A_{j_{i}}\|_{\infty}$ is polynomially bounded in $i$, which, together with (50), establishes the desired result. ∎

We remark that condition (47) is very weak; in fact, we are not aware of an affine system in the literature that would violate it.

We now proceed to what is probably the central result of this paper, namely that neural networks provide optimal approximations for all function classes that are optimally approximated by any affine system with generator function that can be approximated to within arbitrary accuracy by neural networks.

If, in addition, there is a two-dimensional polynomial $\widetilde{\pi}$ such that the weights of $\Phi_{D,\varepsilon}$ are bounded by $|\widetilde{\pi}(D,\varepsilon^{-1})|$, there exist $a>0$ and $c>0$ such that (47) holds, and $\mathcal{C}$ is optimally represented by $\mathcal{D}$ (according to Definition 3.3), then for all $\gamma<\gamma^{\ast}(\mathcal{C})$, there exist a constant $c>0$, a polynomial $\pi$, and a map

The proof follows directly by combining Theorem 5.12 with Theorems 4.2 and 4.3. ∎

Theorem 5.13 reveals a remarkable universality and optimality property of neural networks: All function classes that can be optimally represented by an affine system with generator $f$ satisfying (46) are also optimally representable by neural networks.

α𝛼\alpha-Shearlets and Cartoon-Like Functions

This leads us to the following definition which is a slightly modified version of the corresponding definition in .

Our interest in $\alpha$-shearlets stems from the fact that they optimally represent $\alpha^{-1}$-cartoon-like functions in the sense of Definition 3.3.

This function class was originally introduced in as a model class for functions governed by curvilinear discontinuities of prescribed regularity. In this sense, $\beta$-cartoon-like functions provide a convenient model for images governed by edges or for the solutions of transport equations which often exibit curvilinear singularities.

Using Proposition 3.6, this result allows to conclude that neural networks achieving uniform approximation error $\varepsilon$ over the class $\mathcal{C}$ of cartoon-like functions, with weights represented by no more than $\lceil c\log_{2}(\varepsilon^{-1})\rceil$ bits, for some constant $c>0$, yield an effective best $M$-edge approximation rate of at most $\beta/2$. Theorem 6.8 below demonstrates achievability for $\beta=1/\alpha$, with $\alpha\in[1/2,1]$.

The following theorem states that $\alpha$-shearlets yield optimal best $M$-term approximation rates for $\alpha^{-1}$-cartoon-like functions.

$\widehat{f}(\xi)\neq 0$, for all $|\xi|\leq 1$,

$g$ has at least $7$ vanishing moments in $x_{1}$-direction, i.e.,

The assumptions on the smoothness and the number of vanishing moments of $f$ and $g$ in Theorem 6.4 follow from [46, Eq. 4.9] with $s_{1}=3/2,s_{0}=0,p_{0}=q_{0}=2/3,$ and $|\beta|\leq 4$. While these particular choices allow the statement of the theorem to be independent of $\alpha$, it is possible to weaken the assumptions, if a fixed $\alpha$ is considered. For example, for $\alpha=1/2$ the smoothness assumptions on $f$ and $g$ reduce to $f\in C^{11},g\in C^{28}$.

As our approximation results for neural networks pertain to bounded domains, we require a definition of cartoon-like functions on bounded domains.

We proceed to the main statement of this section.

Moreover, the weights of $\Phi_{D,\varepsilon}$ are polynomially bounded in $D,\varepsilon^{-1}$. It is not difficult to verify that (47) holds and hence Theorem 5.12 yields that $\mathcal{SH}_{\alpha}(f,g,\delta;\Omega)$ is effectively representable by neural networks with activation function $\rho$. Finally, since $\mathcal{E}^{1/\alpha}(\Omega;\nu)$ is optimally representable by $\mathcal{SH}_{\alpha}(f,g,\delta;\Omega)$, we conclude with Theorem 4.3 that $\mathcal{E}^{1/\alpha}(\Omega;\nu)$ is optimally representable by neural networks with activation function $\rho$.

We observe from the proof of Theorem 6.8 that the depth of the networks required to achieve optimal approximation depends on the activation function only. Indeed, for an admissible smooth activation function, inspection of Theorem 5.6 reveals that networks with three layers can produce optimal approximations in Theorem 6.8. On the other hand, if a sigmoidal activation function is employed, Theorem 5.4 shows that the construction in Theorem 6.8 requires a certain minimum depth depending on the order of sigmoidality.

Generalization to Manifolds

Then, we can construct a neural network $\Phi_{i}\in\mathcal{N}\mathcal{N}_{L,M+md,d,\rho}$ according to

where $P_{i}$ denotes the orthogonal projection of $x$ onto the coordinates $(x_{d_{1}},\dots,x_{d_{m}})$. Since $P_{i}$ is linear, $\Phi_{i}$ is a neural network. Moreover, since $P_{i}$ is the inverse of the diffeomorphism $\Xi_{i}$, we get

Such invariances are, in particular, satisfied for all function classes characterized by a particular smoothness behavior, for example, the class of cartoon-functions as studied in Section 6.

Numerical Results

Interestingly, our numerical experiments below indicate that for a fixed, sparsely connected, network topology inspired by the construction of bump functions according to (33) and (34), and with the ReLU as activation function, the stochastic gradient descent algorithm generates neural networks that achieve $M$-edge approximation rates quite close to the fundamental limit.

The network topology we prescribe is depicted in Figure 3. The rationale for choosing this topology is as follows. As mentioned before, admissible smooth activation functions consist of smooth functions which equal a ReLU outside a compact interval. For this class of activation functions, the associated $\alpha$-shearlet generators were constructed from a function $g$ as specified in (34). Choosing $p_{1}=p_{2}=1$ and $p_{3}=2$ in (33) yields hat functions $t$. This construction implies that six nodes are required in the first layer in each subnetwork.

In Figure 3, we see four network realizations of $g$ in parallel. The output layer realizes a linear combination of the subnetworks.

We now train the network using the stochastic gradient descent algorithm. Following (34) the weights of the second layer remain fixed, and the weights in the first and the third layer only are trained. Training is performed for two different functions, where one is a function with a line singularity (Figure 4(a)), and the other one is a cartoon-like function (Figure 5(a)). Specifically, we train the network by drawing samples $(x_{1},x_{2})$ from an equispaced grid in $^{2}$. The resulting error is then backpropagated through the network. We repeat this procedure for different network sizes, i.e., for different numbers of subnetworks.

We start by discussing the results for the function with a line singularity depicted in Figure 4(a). The approximation error corresponding to the trained neural network is shown in Figure 4(b). The faster than linear decay of the approximation error in the semi-logarithmic scale indicates faster than exponential decay with respect to the number of edges. This is consistent with the best $M$-term approximation rate that ridgelets yield for piecewise constant functions with line singularities, see .

It is interesting to observe that the trained subnetworks yield $\alpha$-molecules for $\alpha=0$ (see Figures 4(c)-(e)). These functions are constant along one direction and vary along another, hence can be considered part of a ridgelet system, which is, in fact, an optimally sparsifying representation system for line singularities. Moreover, the orientation of the three learned ridge functions matches that of the original function.

In the second experiment, we draw samples from the function depicted in Figure 5(a) below, which exhibits a curvilinear singularity. Figures 5(c)-(e) show that the corresponding trained subnetworks resemble anisotropic molecules with different scales and of different orientations. We report, without showing the results, that the decay rate of the corresponding approximation error obtained when simply training with different network sizes did not come close to the rate of $M^{-1}$ predicted by our theory. However, with a slight adaptation one obtains the result of Figure 5(b), which demonstrates a decay of roughly $M^{-1}$. The specifics of this adaptation are as follows: We first train a large network with $\sim 10000$ edges, again by stochastic gradient descent. Then, the weights in the last layer are optimized using the Lasso to obtain a sparse weight vector $c^{*}$. We then pick the $M$ largest coefficients of $c^{*}$ and compute the corresponding weighted sum of the associated subnetworks. The resulting approximation error is shown in Figure 5(b). Finally, we investigate whether the approximation characteristics delivered by this procedure are similar to what would be obtained by best $M$-term approximation with standard shearlet systems. Recall that shearlet elements at high scales tend to cluster around singularities . Figures 5(g)-(i) depict the corresponding results. Specifically, Figure 5(g) shows the weighted sum of those subnetworks that have the largest support. In Figure 5(h), we show weighted sums of subnetworks with medium-sized support, and in Figure 5(i) we sum up only the subnetworks with the smallest supports. We observe that, indeed, subnetworks of large support approximate the smooth part of the underlying function, whereas the subnetworks associated to small supports resolve the jump singularity.

Acknowledgments

The authors would like to thank J. Bruna, E. Candès, M. Genzel, S. Güntürk, Y. LeCun, K.-R. Müller, H. Rauhut, and F. Voigtländer for interesting discussions, and D. Perekrestenko for very detailed and insightful comments on the manuscript. G. K. and P. P. are grateful to the Faculty of Mathematics at the University of Vienna for the hospitality and support during their visits. Moreover, G. K. thanks the Department of Mathematics at Stanford University whose support allowed for completion of a portion of this work. G. K. acknowledges partial support by the Einstein Foundation Berlin, the Einstein Center for Mathematics Berlin (ECMath), the European Commission-Project DEDALE (contract no. 665044) within the H2020 Framework Program, DFG Grant KU 1446/18, DFG-SPP 1798 Grants KU 1446/21 and KU 1446/23, and by the DFG Research Center Matheon “Mathematics for Key Technologies”. G. K. and P. P acknowledge support by the DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”.

References