{'fraction_non_alphanumeric': 0.061671231685578885, 'fraction_numerical': 0.017934002869440458, 'mean_word_length': 3.7357422277125796, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximation Rates for Neural Networks with Encodable Weights in Smoothness Spaces

We examine the necessary and sufficient complexity of neural networks to approximate functions from different smoothness spaces under the restriction of encodable network weights. Based on an entropy argument, we start by proving lower bounds for the number of nonzero encodable weights for neural network approximation in Besov spaces, Sobolev spaces and more. These results are valid for most practically used (and sufficiently smooth) activation functions. Afterwards, we derive almost optimal upper bounds for ELU-neural networks in Sobolev norms up to second-order. This work advances the theory of approximating solutions of partial differential equations by neural networks.


Introduction
Deep learning algorithms have lately shown promising results for dealing with classical mathematical problems, such as the solution of partial differential equations (PDEs), see for instance [31,13,22,23,46,12,34,5,16,4,25,44,20,29,18,30]. In this work, we investigate the necessary and sufficient number of non-zero, encodable 1 weights for a vanilla feedforward neural network to approximate functions that are particularly relevant for the solution of PDEs. Notable works in this direction for neural networks with the ReLU (rectified linear unit) activation function are [21,37]. Due to the limited regularity of the ReLU, one is only able to derive approximation rates with respect to first-order Sobolev norms. However, in order to appropriately approximate solutions of fourth-order PDEs, approximation rates with respect to second or higher-order Sobolev norms are required. As an example, consider the Dirichlet problem for the biharmonic operator ∆ 2 (see e.g. [8]) on some domain Ω ⊂ R d , a typical fourth-order problem, which is given by − ∆ 2 u = f, on Ω + boundary conditions. (1.1) In its weak formulation, this operator equation is uniquely solvable in some subspace V (incorporating the boundary conditions) of the Sobolev space W 2,2 (Ω). Additionally (see [8,Section 6]), typical solutions u of (1.1) are even in the Sobolev space W n,2 (Ω) for some n ≥ 3. This motivates studying approximations of Sobolev-regular functions f ∈ W n,p (Ω) by neural networks in higher-order Sobolev norms. In this paper, we make the following two contributions:

I. General Lower Bounds based on Entropy Arguments
Let C ⊂ D be two function spaces. We will lower bound the necessary number for nonzero, encodable weights of neural network approximations of functions from C with respect to the norm in D. Our notion of a lower bound for the number of nonzero, encodable weights can be summarized as follows: For some γ > 0 (depending on C and D) we have: If for every ε > 0 there exists some M ε ∈ N such that every f ∈ C can be ε-approximated by a neural network Φ ε,f (i.e., f − Φ ε,f D ≤ ε) with M ε nonzero, encodable weights, then (up to a logarithmic factor and for some constant C) M ε ≥ Cε −γ .
In [39], the concept of the ε-entropy H ε (C, D) was used to derive lower bounds for M ε for specific choices of C and D. In Theorem 3.3 we generalize that approach to a wide range of function spaces. In detail, we show that every lower bound on the ε-entropy H ε (C, D) of the unit ball of C with respect to · D can directly be transferred to a lower bound on the number of nonzero, encodable weights of an approximating neural network. Concretely, if H ε (C, D) ≥ Cε −γ , then M ε ≥ Cε −γ / log 2 (1/ε). This approach works with fairly general activation functions .
Since lower bounds on the ε-entropy are well-studied for a variety of classical function spaces 2 , we give a nonexhaustive list of concrete lower complexity bounds in Corollary 3.4 for Sobolev and Besov spaces. Appositely to the upper bounds that we present below, we state the following special instance of these results: For C = W k,p (Ω) and D = W n,p (Ω) with n, k ∈ N, n > k and 1 ≤ p ≤ ∞ we have M ε ≥ Cε −d/(n−k) / log 2 (1/ε).

II. Almost Optimal Upper Bounds for ELU-Neural Networks in second-order Sobolev Spaces
Here, we only consider neural networks with the ELU 1 activation function (see [9]) given by α(e x − 1), x < 0, for α = 1. We have chosen the ELU 1 as our object of study for three reasons: (a) its increasing popularity in applications; (b) sufficient smoothness to allow for approximations in Sobolev norms up to order two. In detail, we have ELU 1 | K ∈ W 2,p (K) ∩ C 1 (K) for all compact K ⊂ R, where p ∈ [1, ∞]; 3 (c) Our proof strategy heavily relies on the construction of a partition of unity with neural networks. This is at least approximately possible with the ELU. Other activation functions of interest are subject to future work. We consider the function spaces C = W n,p ((0, 1) d ) as well as D = W k,p ((0, 1) d ), where n ∈ N ≥k+1 , k ∈ {0, 1, 2} and 1 ≤ p ≤ ∞.
• For the case k ∈ {0, 1}, we construct in Proposition 4.1 for every approximation accuracy ε > 0 and every f in the unit ball of W n,p ((0, 1) d ) a neural network Φ ε,f with at most Cε −d/(n−k) nonzero weights • For the case k = 2, we were not able to show the canonical upper bound ε −d/(n−2) , but get arbitrarily close to it. In detail, for every µ > 0 we construct a neural network, with at most Cε −d/(n−2−µ) nonzero weights such that f − Φ ε,f W 2,p ≤ ε.
In both cases the depth of the constructed networks is constant (i.e. accuracy-independent) and greater than two. 4 In Theorem 4.2, we additionally show that the weights of Φ ε,f can be encoded by C log 2 (1/ε) bits.
We note that, similarly to [51,21,39], the main proof strategy is based on the approximation of localized polynomials by neural networks. However, constructing localized bumps that together form a partition of unity with ELU-neural networks is highly-nontrivial and can only be done approximatively.
As already outlined in [21,Section 1.4], we observe in both, lower and upper bounds, a trade-off between the complexity of the approximating neural networks and the order of the approximation norm: A higher order of k requires neural networks with asymptotically more nonzero weights. Additionally, up to a log-factor and up to µ > 0 for k = 2, our upper bounds are tight if we only allow encodable weights.

Related Work
The universal approximation theorem [10,24] is often regarded as the starting point of approximation theory for neural networks. It shows that every continuous function defined on a compact domain can be uniformly approximated by shallow neural networks with continuous, non-polynomial activation function. Extensions of this theorem (see [40,Section 4] and the references therein) also take derivatives into account. In more detail, it has been established that shallow neural networks with sufficiently regular activation function and unrestricted width are dense in the space C m , where m ∈ N. The necessary and sufficient complexity of neural network approximations for (piecewise) smooth functions has been studied, for example, in [51,27,2,48,43,45] for ReLU-neural networks and in [3,35,6,36,32,49,33] for neural networks with activation functions that have higher regularity. The approximation error in all of these papers is measured with respect to L p -norms. In particular, we mention [36,Theorem 4.1], which is applicable to ELU-neural networks and establishes bounds for Hölder functions in L ∞ . The papers [6,39] consider the restriction of encodable weights.
In this paper we are primarily interested in the approximation of functions with respect to Sobolev norms. In this direction, we mention two works, which examine the approximation capabilities of ReLUneural networks with respect to W 1,p norms. The paper [21] derives lower complexity bounds based on a VC dimension argument for unrestricted neural network weights (similar to the one presented in [51]) and upper bounds based on the emulation of localized polynomials. In [37] approximation rates were derived by re-approximating finite elements. None of these papers examine neural networks with encodable weights.

Outline
After having introduced the necessary terminology for neural networks in Section 2, we start by proving general lower complexity bounds in Section 3. In Section 4, we derive almost optimal upper approximation rates for ELU-neural networks. The proofs of the two main results in this section, Proposition 4.1 and Theorem 4.2, can be found in Appendix D and Appendix E, respectively. To not interrupt the flow of reading, the notation section, basic facts about Sobolev spaces and basic operations one can perform with neural networks have been deferred to Appendices A-C, respectively.

Neural Networks with Encodable Weights: Terminology
We start by formally introducing neural networks closely sticking to the notions introduced in [39]. In the following, we will distinguish between a neural network as a structured set of weights and the associated function implemented by the network, called its realization. Towards this goal, let us fix numbers L, d = N 0 , N 1 , . . . , N L ∈ N.
• A family Φ = (A , b ) L =1 of matrix-vector tuples of the form A ∈ R N ,N −1 and b ∈ R N is called neural network.
• We refer to the entries of A , b as the weights of Φ and call M (Φ) := L =1 ( A 0 + b 0 ) its number of nonzero weights, L = L(Φ) its number of layers and we call N the number of neurons in layer .
• We denote by d := N 0 the input dimension of Φ and by N L the output dimension.
• Moreover, we set which is the maximum absolute value of all weights.
• For defining the realization of a network Φ = (A , b ) L =1 , we additionally fix an activation function : where x L results from the following scheme: and where acts componentwise.
• We denote by N N d the set of all -realizations of neural networks with input dimension d and output dimension 1. 5

Encodability
In the following, we study neural networks with encodable weights. This information-theoretic viewpoint has already been examined in [6,39] and is motivated by the observation that on a computer only weights of limited complexity (w.r.t. their bit-length) can be stored. In this paper, we consider weights that can be encoded by bit-strings with length logarithmically growing in 1/ε, where ε is the approximation accuracy.
To make the notion of encodability more precise, we first introduce coding schemes (see [39]): A coding scheme (for real numbers) is a sequence B = (B ) ∈N of maps B : {0, 1} → R. Now we define sets of neural networks with weights encodable by a coding scheme. Given an arbitrary coding scheme B = (B ) ∈N , and d ∈ N, ε, M > 0, we denote by the set of all neural networks Φ with d-dimensional input, one-dimensional output and at most M nonzero weights such that each nonzero weight of Φ is contained in Range(B C0 log 2 (1/ε) ).

Lower Bounds For Neural Networks with Encodable Weights and General Activation Functions
In this section, we derive lower bounds on the necessary number of nonzero, encodable weights of neural network approximations. The approximated function spaces include a wide variety of classical smoothness spaces and the accuracy is measured in rather general norms. For this, we only assume mild conditions on the activation function of the neural network. We note that the proof of our result is essentially an abstract version of the proof of [39,Theorem 4.2]. After encouragement of one of the authors 6 of [39] and after studying the paper more closely, we noticed that it is possible to consider the proof strategy of [39,Theorem 4.2] in a very general setting which we will outline below. Throughout this section (unless stated otherwise) we fix some d ∈ N, some domain Ω ⊂ R d and two normed spaces C, D of (equivalence classes of) functions defined on Ω with values in R. Additionally, we assume that C ⊂ D.
Definition 3.1. Let C 0 > 0 be fixed. Additionally, let f ∈ C, and for some function : R → R assume that N N d ⊂ D. Finally, let ε > 0 and fix some coding scheme B. Then, for C 0 > 0, we define the quantities 7 In other words, the quantity M B ε (f ) denotes the required number of nonzero weights of a neural network Φ to ε-approximate f with weights that can be encoded with C 0 log 2 (1/ε) bits using the coding scheme B. M B ε (C, D) gives a uniform bound of this quantity over the unit ball in C. Next, we introduce the entropy H ε (C, D), for which we show in Theorem 3.3 that it can directly be related to the approximation capabilities of neural networks.

Definition 3.2 ([28]
). For ε > 0, define U ε (C, D) as the minimal number of closed balls with radius ε in the space D needed to cover the unit ball in C embedded in D. The ε-entropy of the unit ball of C embedded into D is then defined by Theorem 3.3 now states that if we can lower bound the ε-entropy, then we are also able to lower bound M B ε (C, D). Lower bounds on the ε-entropy (and hence for the quantity M B ε (C, D)) for specific, frequently used function spaces fulfilling the assumptions of the theorem will be given in Corollary 3.4. Theorem 3.3. Let : R → R with (0) = 0 and such that N N d ⊂ D. Additionally, assume that H ε (C, D) ≥ C 1 ε −γ for some γ = γ(C, D), C 1 = C 1 (C, D) > 0 and all ε > 0. Then, for each C 0 > 0 there exists a constant C = C(γ, C, D, C 0 ) > 0, such that for each coding scheme of real numbers B, and for all ε ∈ (0, 1 /2) we have Proof . The proof of the theorem is along the lines of [39,Theorem 4.2] (see page 34 of the corresponding arXiv version), but in a more abstract setup. We shortly describe the idea. Afterwards we describe how one needs to adapt the quantities of the proof of [39,Theorem 4.2] in order to prove our result. First of all, we need the notion of the minimax code length L ε (C, D) of C with respect to D. The minimax code length describes the uniform description complexity of the set {f ∈ C : f C ≤ 1} in terms of the number of nonzero bits necessary to encode every f with distortion at most ε in D. It is defined as follows (see also [39,Definition B.2]): 6 We want to take the opportunity to thank Philipp Petersen for the fruitful suggestion. 7 we use the convention that min ∅ = ∞.
Let ∈ N. We denote by E := E : C → {0, 1} the set of binary encoders mapping elements of C to bit strings of length , and by D := {D : {0, 1} → D} the set of binary decoders mapping bit-strings of length into D. For ε > 0, we define the minimax code length by By [11,Remark 5.10] it holds that L ε (C, D) ≥ H ε (C, D) and, thus, since we assumed H ε (C, D) ≥ C 1 ε −γ , we get L ε (C, D) ≥ C 1 ε −γ . Now we prove the claim by contradiction: Assume that the lower bound (3.1) does not hold. Then, for every f ∈ C, f C ≤ 1 there exists some neural network Φ ε,f ∈ N N B M, C0 log 2 (1/ε) ,d such that (a) its -realization approximates f up to error ε in D and (b) it has M < Cε −γ / log 2 (1/ε) nonzero weights. In [39,Lemma B.4] it is shown that there exists an injective map Γ : We define an encoder and decoder as and where Γ −1 is the left-inverse of Γ. We now get that which is a contradiction to L ε (C, D) ≥ C 1 ε −γ . We close this proof outline by demonstrating how to replace the quantities in the proof of [39,Theorem 4.2] in order to prove our result.
K 0 , C 2 equally defined, We proceed by listing a variety of lower bounds for specific examples for frequently used function spaces.
(ii) Sobolev Spaces: Let s, t ∈ N with t > s and let p ∈ (0, ∞]. Then, for C = W t,p (Ω) and for D = W s,p (Ω) there exists some C > 0 with Proof . (i) follows immediately from Theorem 3.3 in combination with Theorem [15, Section 3.5].
(ii) follows from Theorem 3.3 together with [14, Section 1.3], where we use the estimate on the approximation number a k (id) (cf. page 9) combined with the relation of a k (id) and the entropy.

Discussion
We conclude this section by a discussion putting our results into context.
(i) Activation Functions: Apart from having sufficient regularity, the only other requirement on the activation function present in our lower bounds is (0) = 0. Hence, we are in a position to conclude suitable lower bounds for many practically used activation functions such as the (leaky) ReLU, the ELU, the inverse (linear) square root unit, rectified power units, the tanh, the arctan, and more.
(ii) Other Function Spaces: As already mentioned above, one can deduce similar lower bounds for other choices of C, D. Notable examples include Hölder spaces, Triebel-Lizorkin, or Zygmund spaces (see for instance [50,15] and the references therein for further examples).
(iii) Relation to Lower and Upper Bounds With Non-Encodable Weights: If one drops the restriction of encodable weights and considers the more general setting of arbitrary weights, a lesser number of weights is required in general. For this setting, we mention the results from [52,21] which combined state: For C = W n,∞ ((0, 1) d ) and D = W k,∞ ((0, 1) d ) with k = 0, 1, it holds for the necessary number of nonzero weights M ε to achieve an ε-approximation in W k,∞ norm that For k = 0, in [52] neural networks are constructed that achieve this approximation rate. In comparison, our entropy bounds show that under the assumption of encodable weights M ε ≥ Cε −d/(n−k) (suppressing the log 2 ( 1 /ε) factor for simplicity of exposition).
4 Upper Bounds for Function Approximation by ELU Neural Networks in W k,p for k = 0, 1, 2 In this section, we show that for an arbitrary accuracy ε > 0, every function from the unit ball of Sobolev space W n,p (with n > k) can be ε-approximated in weaker Sobolev norms W k,p with order k = 0, 1, 2 by an ELU-neural network. For this, we explicitly construct approximating neural networks with constant depth (i.e., independent of ε) and give upper bounds for the number of nonzero, encodable weights (depending on ε), which in the light of the results of Section 3 are almost optimal. The ELU activation function is parametrized by α > 0 which determines the function for x < 0. We have that for every compact subset K of R and every p ∈ [1, ∞]. Since the regularity of the neural network is determined by the regularity of the activation function, approximations in W 2,p norm can only be shown for the case α = 1 (see Figure 1 for a visualization). We exclusively consider this case in our theorem and proofs. In the discussion at the end of this section, we shortly note that our results can be adapted to α ∈ (0, 1) and give an outlook how our proof strategy might be applied in a plug-and-play manner to different activation functions.  The proof of the main statement of this section can be roughly divided into two steps: First (see Proposi-tion 4.1), the approximating neural networks are constructed with weights whose absolute values are bounded polynomially in ε −1 . In Theorem 4.2, the encodability of the weights is enforced. Note that for the case k = 2 we can only get arbitrarily close to the best possible approximation rate. Towards this end, we introduce, for µ > 0, the notation We start with Proposition 4.1.
Proposition 4.1. Let d ∈ N, k ∈ {0, 1, 2}, n ∈ N ≥k+1 , 1 ≤ p ≤ ∞, and µ > 0. Then, there exist constants L, C, θ, ε depending on d, n, p, k, µ with the following properties: For every ε ∈ (0, ε) and every f ∈ F n,d,p , there is a neural network Φ ε,f with d-dimensional input and one-dimensional output, at most L layers and at most Cε −d/(n−k−µ (k=2) ) nonzero weights bounded in absolute value by Cε −θ such that Proof . The proof of this proposition is the subject of Appendix D. Here, we shortly outline the proof strategy. The main idea is based on the common strategy (see e.g. [51,21,36]) of approximating f by localized polynomials which in turn are approximated by neural networks. For this, one needs to approximate bump functions that form a partition of unity as well as polynomials up to degree n − 1 by neural networks.
• For a gridsize 1/N (with N ∈ N) we divide the domain (0, 1) d into (N + 1) d equally large patches. In Appendix D.1, we construct for each patch (abbreviated by p) a bump function φ p ∈ W 2,∞ with rescaled shifts of ELU 1 . Deviating from usually used bump functions, our φ p are not compactly supported on the corresponding patch (but decay exponentially fast outside the patch for N → ∞) and their sum only approximates • Using the Bramble-Hilbert Lemma B.4 and our bump functions from Appendix D.1, we show in Appendix D.2 that every function f ∈ F n,d,p can be approximated in · W k,∞ (for k = 0, 1, 2) up to error (1/N ) n−k by localized (averaged Taylor) polynomials of the form φ p · poly p .
• In Appendix D.3, we show that the localized polynomials φ p · poly p can be approximated by ELU 1neural networks (Lemma D.11). Since the bumps φ p are by construction ELU 1 -neural networks, we only need to approximate the polynomials (Proposition D.7) and deal with the multiplication of φ p with poly p (Propositions D.9 and D.10).
• In Appendix D.4, we put everything together and choose N = N (ε) appropriately.
The main theorem now states that Proposition 4.1 also holds with encodable weights, i.e. for each ε > 0, every element of the set of weights W ε = f W ε,f (where W ε,f denotes the weights of Φ ε,f ) can be uniquely encoded by C log 2 (1/ε) bits. To state this in a formal way, we use the notation introduced in Equation (2.1).
Then, there exist constants L, C and ε, and a coding scheme B = (B ) ∈N depending on d, n, p, k, µ with the following properties: For every ε ∈ (0, ε) and every f ∈ F n,d,  increasing N (i.e. finer grid with more bumps), the distance to 1 (0,1) will decrease exponentially fast.
Proof . We give a short outline of the proof here, the details can be found in ) be the network from Proposition 4.1 (where the main work has already been done). We denote the collection of entries of and use that they are independent of f (i.e., they only depend on ε, n, d, p, k, µ). Only the weights A L , b L in the last layer depend on f .
• We round the entries of where we also use the fact that the weights of Φ ε,f are bounded in absolute value by Cε −θ .
Hence, the weights of the approximating neural networks can be chosen from a set W ε with less than ε −s real numbers, where s > 0 only depends on d, n, p, k, µ and not on f . Consequently, there exists a surjective mapping B ε : {0, 1} s log 2 (1/ε) → W ε . The collection of these maps constitutes the coding scheme.

Discussion
We discuss the tightness of our bounds, possible extensions, and differences to other works.
(i) Tightness of the Bounds: From Corollary 3.4 (ii) it follows that our bounds for encodable neural network weights are tight up to a log factor for k = 0, 1. For k = 2 we get arbitrary close to the optimal bound (again up to a log factor) but were not able to reach it. If we allow for arbitrary weights, then this upper bound might be drastically improved (see also (iii) in the discussion of Section 3).
(iii) Difference to Other Works: As we have already remarked in the proof outline of Proposition 4.1, reapproximation of localized polynomials is a common strategy to obtain neural network approximation results (see e.g. [51,21,36]). Our work differs from these other works in three major aspects: (a) Our approximations include W 2,p (instead of maximally W 1,p ).
(b) Constructing a partition of unity with ELU-neural networks is tricky (contrary to ReLU networks) and can only be done approximately (see proof outline of Proposition 4.1 and Figure 2).
(c) ELU-neural networks admit approximations of polynomials with a depth independent of ε, which results in constant-depth approximations of f .
(iv) Plug-and-Play: We believe that our proof strategy can be used in a plug-and-play fashion with various activation functions. So far the concept of re-approximating localized polynomials (which goes back to [51]) has mainly been used for ReLU-like activation functions that allow the construction of an exact partition of unity. In our setting, an approximate partition of unity suffices. This might open the door for results involving e.g. the inverse square root unit, the softplus function, or sigmoidal functions. For instance, the approximative partition of unity introduced in [33] for L ∞ could potentially be used as a starting point for deducing approximation rates in Sobolev spaces of sigmoidal neural networks. However, we believe that every approximation result with respect to norms in W k,p with k ≥ 3 gets increasingly technical.

A Notation and Auxiliary Results
In this subsection, we depict the (mostly standard) notation used throughout this paper. We set N := {1, 2, . . .} and N 0 := N∪{0}. For k ∈ N 0 we define N ≥k := {k, k +1, . . .}. For a set A we denote its cardinality by |A| ∈ N ∪ {∞} and by 1 A its indicator function of A. If x ∈ R, then we write x := min{k ∈ Z : k ≥ x} where Z is the set of integers and x := max{k ∈ Z : k ≤ x}. If d ∈ N and · is a norm on R d , then we denote for x ∈ R d and r > 0 by B r, · (x) the open ball around x in R d with radius r, where the distance is measured in · . By |x| we denote the euclidean norm of x and by x ∞ the maximum norm. We endow R d with the standard topology and for A ⊂ R d we denote by A the closure of A.
For d 1 , d 2 ∈ N and a matrix A ∈ R d1,d2 the number of nonzero entries of A is counted by · 0 , i.e.
If f : X → Y and g : Y → Z are two functions, then we write g • f : X → Z for their composition. If additionally U ⊂ X, then f | U : U → Y denotes the restriction of f onto U . We use the usual multiindex notation, i.e. for α ∈ N d 0 we write |α| := α 1 + . . . + α d and α! : Let from now on Ω ⊂ R d be open. For a function f : Ω → R, we denote by its (weak or classical) derivative of order α. For n ∈ N 0 ∪ {∞}, we denote by C n (Ω) the set of n times continuously differentiable functions on Ω. Additionally, if Ω is compact, we set, for f ∈ C n (Ω) We denote by L p (Ω), 1 ≤ p ≤ ∞ the standard Lebesgue spaces.
In the following, we will also make use of the following well-known fact stating that the exponential function decays faster than any polynomial.
This implies that for all γ > 0 there exists some constant C = C(α, β, γ) > 0 such that for all x > 0 there holds

B Sobolev Spaces
In this section, we introduce Sobolev spaces (see [1]) which constitute a crucial concept within the theory of PDEs (see e.g. [42,17]).
and is equipped with the norm and we equip this space with the norm f W n,∞ (Ω) := max |α|≤n D α f L ∞ (Ω) . Moreover, for 0 ≤ k ≤ n, on W n,p (Ω) we introduce the family of semi-norms respectively.
where C = C(n, p, d) is the norm of the extension operator.
The following lemma which will be crucial for the proofs of our results can be stated in much more generality (see [7,Chapter 4.1]) and relies on the use of averaged Taylor polynomials. We only state a version tailored to our specific needs and will not give a proof since the details of this specific version have been worked out in [21, Section B.3 and Lemma C.4].
Now we turn our attention to a version of a product rule tailored to our needs.
Lemma B.5. Let k ∈ {0, 1, 2}, f ∈ W k,∞ (Ω) and g ∈ W k,p (Ω) with 1 ≤ p ≤ ∞, then f g ∈ W k,p (Ω) and there exists a constant C = C(d, p) > 0 such that and, consequently Proof . For k = 0 the statement is obvious. For k = 1 we get from [21,Lemma B.6] that there exists a constant C = C(d, p) > 0 such that from which the statement can easily be deduced. For k = 2 it follows from [19,Chap. 7.3] that the usual product rule also holds for the second order derivatives such that we have Again the overall statement follows easily.
The following corollary establishes a chain rule estimate for W 2,∞ .
Corollary B.6. Let d, m ∈ N and Ω 1 ⊂ R d , Ω 2 ⊂ R m both be open, bounded, and convex. Then, there is a constant C = C(d, m) > 0 with the following property: Proof . The result can be shown by basic computations using the classical first derivative and [21, Corollary B.5, Lemma B.6].

C Neural Network Calculus
In this section, we introduce several operations one can perform with neural networks, namely the implementation of the identity function, the (sparse) concatenation and the parallelization.
A useful tool when constructing approximations of functions by neural networks is to be able to implement the identity function with a neural network. This is for example possible for ReLU-neural networks with an arbitrary number of layers and a moderate number of nonzero weights (see [39]). For arbitrary activation functions, however, this is in general not possible. One way to circumvent this problem is to use local approximations of the identity (see e.g. [38,Proposition B.3]). However in case of the ELU, we can use a simpler strategy. For non-negative x the ELU is already defined as the identity. By shifting we can construct an ELU-neural network implementing the identity function on [−B, ∞) d for an arbitrary but fixed B ≥ 0.
(ii) L layers; Proof . For L = 1 the claim is obvious. For L ∈ N ≥2 the claim follows from the observation that Next, we consider the concatenation of two neural networks as given in [39].
be two neural networks such that the input dimension of Φ 1 is equal to the output dimension of Φ 2 . Then the concatenation of Φ 1 , Φ 2 is defined as the L 1 + L 2 − 1-layer neural network It is easy to see that . However, it is not clear how the number of nonzero weights of Φ 1 Φ 2 relates to M (Φ 1 ) and M (Φ 2 ). This motivates the definition of a sparse concatenation, which is a slight adaption from [39] and makes use of the identity result from Proposition C.1.
Then, the sparse concatenation of Φ 1 and Φ 2 is defined as B is the neural network as defined in Proposition C.1. We have Proof . The proof of (i) and the fact that L(Φ 1 Φ 2 ) = L 1 + L 2 immediately follows from the definition of the concatenation of two neural networks in combination with Proposition C.1. Moreover, it is not hard to see that from which the other statements follow.
In the next lemma we introduce the parallelization of neural networks with a potentially different number of layers. This result relies again on the identity implementation from Proposition C.1.
It is easy to see that (i) and (ii) hold. Furthermore, we have and, finally,

D Proof of Proposition 4.1
The goal of this section is the proof of Proposition 4.1. For an overview of the required steps see the proof outline below Proposition 4.1.

D.1 Approximate Partition of Unity by ELU-neural networks
We start with the proof of the existence and technical details of the approximate partition of unity. First of all, we give the definition of the involved bump functions whose sum approximates the 1-function on (0, 1) d (see Figure 3 for an illustration for the case d = 1).
Definition D.1. For a scaling factor s ≥ 1 we define the scaled ELU by Moreover, we define a scaled one-dimensional bump function by and, for d, N ∈ N and m ∈ {0, . . . , N } d we define multi-dimensional bumps φ s m : R d → R as a tensor product of scaled and shifted versions of ψ s . Concretely, we set Finally, the collection of bump functions is denoted by Ψ := {φ s m : m ∈ {0, . . . , N } d }.
Note that the φ s m do not have compact support but (as we will see in Proposition D.3) decay exponentially fast. Before we state the corresponding result, we first need a technical result for the one-dimensional functions ψ s . For a reader more interested in the overall properties of the partition of unity we suggest to skip the lengthy computations of the following lemma and directly jump to Proposition D.3.
Lemma D.2. Let s ≥ 1, N ∈ N, and k ∈ {0, 1, 2}. Then there exists some absolute constant C > 0 such that for all m ∈ {0, . . . , N } we have Proof . Let x ∈ R. First of all, we note Hence, we have for the first classical derivative and for the second order weak derivative We start with k = 0 and for this we estimate ψ s 3N x − m N (x) for x from different intervals. Keep in mind that s ≥ 1. Case On the one hand we have On the other hand we have Then, on the one hand we have On the other hand we obtain that On the other hand, we have Combining the two estimates we get In total, we obtain and, consequently, for s ≥ 1, we have We proceed with estimating the first and second derivatives. First of all, it is clear that for all i ∈ Z and x ≤ i 3N + m N and for all j ≥ i we have Hence, by using the triangle inequality on every of the involved summands as well as the properties of x with respect to the considered cases we obtain The following result establishes the properties we need from our approximate partition of unity. In particular, we need to control the Sobolev norm of the bump functions; show that the bumps, which do not have compact support, decay sufficiently fast outside a ball containing their center; show that the sum of the bumps approximates 1 (0,1) d in W 2,∞ ; and, finally, that the bumps can be implemented by an ELU-neural network. The last property is not very surprising since was exactly the motivation for the construction of the bumps.
In particular, if we choose s = N µ for an arbitrary µ > 0, for all γ > 0 and some C = C (µ, γ, k, d) > 0 there holds (iv) let µ > 0, then there exists N 1 = N 1 (µ) ∈ N such that ≤ CN k s k−1 e −s for s = N µ and N ≥ N 1 ; (v) For each φ s m ∈ Ψ there is a neural network Φ s m with d-dimensional input and d-dimensional output, with two layers and C nonzero weights, that satisfies which implies that |φ s m,I | W 1,∞ (R |I| ) ≤ C |I| N . Finally, let additionally be j ∈ I be arbitrary. If i = j then we have that (by using (D.1) in combination with Lemma D.2 for k = 2) that Moreover, if i = j, then, if we set I := I \ {i, j} we obtain with similar arguments as before that where we assumed w.l.o.g. that i < j. This implies |φ s m,I | W 2,∞ (R |I| ) ≤ C |I| N 2 s, which yields the claim. ad (iii): For x ∈ R, we set Θ s (x) := e s(3N x−3m+2) − e s(3N x−3m+1) − e s(3N x−3m−1) + e s(3N x−3m−2) = e 3s(N x−m) · e 2s − e s − e −s + e −2s and get Hence, we have Furthermore, for every x ∈ R such that x ≤ − 5 6N + m N we have by the triangle inequality that Trivially, we also have |Θ s (x)| ≤ Ce − 1 2 s for all x ≥ 5 6N + m N . Hence, for k ∈ {0, 1, 2} we conclude directly that This shows that |φ s m | W 0,∞ (Ω exp m ) ≤ C d s e − 1 2 s . By proceeding in a similar manner and with the same techniques as in the proof of (ii) and combining these with Equation (D.2), one can show the remaining Sobolev seminorm estimates for the higher-order derivatives. The "in-particular" part then follows from Proposition A.1.
ad (iv): We start with an observation for the case d = 1 that will be helpful later in the multi-dimensional case. For this, let x ∈ R. Then where we used in the second step that this is a telescope sum. The multi-dimensional case can now be broken down to the same sum. We have for x ∈ R d that On the other hand, for the second two terms of the sum (D.4), we have Now, we can estimate for a constant C = C(d) > 0. Next, we observe that ad (v): By using the definition of ψ s and s we get for l = 1, . . . , d. Now it is easy to see that there is a neural network Φ s m with d-dimensional input and d-dimensional output, with two layers, C nonzero weights, that satisfies

D.2 Approximation by localized polynomials
With the help of the bump functions from Appendix D.1 and averaged Taylor polynomials, we are in a position to approximate any f ∈ W n,p ((0, 1) d ) by localized polynomials in higher-order Sobolev norms. The following proposition provides the details.
and Before we prove Lemma D.4, we state and prove an auxiliary result. The estimation will be very rough and can for sure be improved. This is, however, not necessary for our purpose. Proof . We start with bounding the norm of the polynomial by using the triangle inequality. There holds Using that Ω m,N ⊂ B 2, · ∞ we get If we now combine Remark D.5 with Equation (D.6), we get where we have additionally used Remark B.3 in the last step. Finally, we can estimate, by the triangle inequality where we again used the extension property from Equation (B.1) for the first step.
Proof of Lemma D.4 . We use approximation properties of the polynomials from the Bramble-Hilbert Lemma B.4 to derive local estimates and then combine them using an approximate partition of unity to obtain a global estimate. In order to use this strategy also near the boundary, we make use of an extension operator (see Remark B.3).
Step Furthermore, similarly to [21,Lemma C.4], we obtain the estimate Then and we have (by using Lemma B.5 in the first step), that Then, by Proposition A.1, there exists Step for all N ≥ N 1 . Here we used Step 1 to bound the first term of the sum and Step 2 for the second.
Step 4a (Partition of Unity): For the first term in Equation (D.8), we get by the product rule from Lemma B.5 for all N ≥ N 2 = N 2 (µ). For the second inequality we used the same trick as in Step 2 which is based on Proposition A.1.
Step 4b (Patches): Considering the second term from Equation (D.8), we obtain for each m ∈ {0, . . . , (D.10) The term ( ) can be handled with Step 1, the term ( ) with Step 3 and the third one ( ) with Step 2. Since ( ) and ( ) require a similar strategy we only demonstrate it for the third term. We get from Step 2 We can now bound the sum from Equation (D.10) for each m ∈ {0, . . . , N } d by (D.11) Consequently, we get Step 4a finally yields

D.3 Approximation of Localized Polynomials by Neural Network Realizations
The goal of this section is now to approximate the localized polynomials from Appendix D.2 by neural networks.
We start by approximating monomials on R by two-layered neural networks with (rather general) activation functions that have non-vanishing Taylor coefficients up to order n ∈ N. The construction is mainly based on finite backward differences in combination with ideas from [41]. We note that the statement can be simplified in case of the ELU-activation function. However, since we believe this result to be an interesting contribution in itself, we have formulated in this generality.
Remark D.8. The assumptions of Proposition D.7 apply to the activation function ELU α for all α ∈ R \ {0} and for an arbitrary n ∈ N. One only needs to choose an arbitrary x 0 < 0 for which we have that With the help of Proposition D.7, we are now in a position to construct neural networks which implement an approximate multiplication.
Proposition D.9. Let : R → R and x 0 ∈ R such that is three times continuously differentiable in a neighborhood of x 0 and (x 0 ) = 0. Let B > 0, then there exists a constant C = C(B, ) > 0 such that for every ε ∈ (0, 1 /2), there is a neural network × with two-dimensional input and one-dimensional output that satisfies the following properties: (iv) × max ≤ Cε −2 .
Proof . Let C be the constant from Corollary B.6 and set ε := ε /2C. Proposition D.7 yields that there exists a neural network Φ 2 ε with 2 layers and at most 9 nonzero weights such that for all k ∈ {0, 1, 2} we have As in [51], we make use of the polarization identity In detail, we define the neural network which fulfills for all (x, y) ∈ R 2 that and directly see for k = 0 that For the case k = 0 and k = 1 we first note that The composition rule from Corollary B.6 then yields that In the same way, we get and, thus, claim (i) is shown. Finally, we have for k ∈ {0, 1, 2} for a constant C 1 = C 1 (B) > 0, yielding (ii). Claim (iii),(iv) immediately follow from the construction of × ε in combination with Proposition D.7.
Proposition D.9 is the foundation for the following results which implements a neural network that approximates the multiplication of multiple inputs: Lemma D. 10. Let d, m, K ∈ N and N ≥ 1, µ, c > 0 be arbitrary, and let = ELU 1 . Then there are constants C(d, m, c) > 0 such that the following holds: For any ε ∈ (0, 1 /2), and any neural network Φ with d-dimensional input and m-dimensional output and with number of layers and nonzero weights all bounded by K, such that for k ∈ {0, 1, 2}, l = 1, . . . , m and x ∈ (0, 1) d there exists a neural network Ψ ε,Φ with d-dimensional input and one-dimensional output, and with (i) number of layers and nonzero weights all bounded by CK; Proof . We show by induction over m ∈ N that the statement holds. To make the induction argument easier we will additionally show that the network Ψ ε,Φ can be chosen such that the first L(Φ) − 1 layers of Ψ ε,Φ and Φ coincide. If m = 1, then we can choose Ψ ε,Φ = Φ for any ε ∈ (0, 1 /2) and the claim holds. Now, assume that the claim holds for an arbitrary, but fixed m ∈ N. We show that it also holds for m + 1. For this, let ε ∈ (0, 1 /2) and let Φ = ((A 1 , b 1 ), (A 2 , b 2 ), . . . , (A L , b L )) be a neural network with d-dimensional input and (m + 1)-dimensional output and with number of layers, and nonzero weights all bounded by K, where each A l is an N l × N l−1 matrix, and b l ∈ R N l for l = 1, . . . L.
Step 1 (Invoking induction hypothesis): We denote by Φ m the neural network with d-dimensional input and m-dimensional output which results from Φ by removing the last output neuron and corresponding weights. In detail, we write Using the induction hypothesis we get that there is a neural network with d-dimensional input and one-dimensional output, and at most KC layers and nonzero weights such that and |R (Ψ ε,Φm )| W k,∞ ((0,1) d ) ≤ CN k+µ (k=2) . Moreover, we have that Φ m max ≤ Φ max , so that there we can estimate Ψ ε,Φm max ≤ C max{ Φ max , ε −2 }. Furthermore, we can assume that the first L − 1 layers of Ψ ε,Φm and Φ m coincide and, thus, also the first L − 1 layers of Ψ ε,Φm and Φ, i.e. A l = A l for l = 1, . . . , L − 1.
ad (ii): The first L − 1 layers of Ψ ε,Φ and Φ coincide and for the approximation properties it holds that .
(D. 18) We continue by considering the first term of the Inequality (D.18) and bound the k-semi-norm of this term. Since the case k = 2 is the most complicated one and k ∈ {0, 1} can be shown similarly, we only state the case k = 2. We apply the chain rule from Corollary B.6 for g : where we used the induction hypothesis together with |[R (Φ)] m+1 | W k,∞ ((0,1) d ) ≤ cN k+µ (k=2) in the third step and assumed that c ≤ C. Similarly, we can show the bound CεN k for for the k-semi-norms with k ∈ {0, 1}. Combining the statements of the semi-norms then yields the required bound for the norm. To estimate the second term of (D.18) we apply the product rule from Lemma B.5 and get for k ∈ {0, 1, 2}. For the second step, we used again the induction hypothesis together with

Combining (D.18) with (D.19) and (D.20) yields
ad (iii): Next, we show that Again, we only show the case k = 2. The other cases can be shown in the same way. Similarly as in (D. 19) we have that where Corollary B.6 was used for the second step and Proposition D.9 (ii), together with an argument as in (D. 19), implies the third step. ad (iv): Finally, we need to derive a bound for the absolute values of the weights. From the definition of Ψ ε,Φ and Lemma C.3 we get From × max ≤ Cε −2 (see Proposition D.9 (iv)) and Ψ ε,Φ max ≤ C max{ Φ max , ε −2 } (see Step 2) it follows that Ψ ε,Φ max ≤ C max{ Φ max , ε −2 }. This concludes the proof.
In the last part of this subsection, we are finally in a position to construct neural networks which approximate sums of localized polynomials. Then there is a neural network Φ P,ε = Φ P,ε (f, d, n, N, µ, ε) with d-dimensional input and one-dimensional output, with at most C layers and C(N + 1) d nonzero weights, such that Proof .
Note that the network Φ P,ε only depends on p f,m (and thus on f ) via the coefficients c f,m,α .
Step 3 (Estimating the approximation error in · W k,p ): We get This concludes the proof.

D.4 Putting Everything Together
Now we conclude the proof of Proposition 4.1.

E Encodable Weights and Proof of Theorem 4.2
In this section, we investigate how rounding errors of the weights in the last layer affect the approximation error of a neural network. For this, the next lemma shows that under some conditions on the growth of the activation function and on the functions implemented by the first up to the next-to-last layer, the error resulting from rounding the weights in the last layer can be controlled in the |·| W k,∞ (Ω) semi-norm for k = 0, 1, 2. The following lemma could be stated in more generality, in particular, the conditions on the activation function could be weakened. However, to simplify the exposition, we took only care that the conditions are satisfied by the ELU 1 .
Proof . ad (i): We set ν := s 1 + s 2 + 2 and have where we have used in the last step that ε ≤ 1 /2. ad (ii): We define ν := s 1 + s 2 + 1 + log 2 (C), where C ≥ 1 is the constant from Corollary B.6 and get in a similar manner as in (i) that where we used in the third step that C = 2 log 2 (C) ≤ ε − log 2 (C) . Combining this observation with (i) yields the claim. ad (iii): Using the same steps as above we set ν := 2s 1 + 2s 2 + 1 + log 2 (C), where C ≥ 1 is again the constant from Corollary B.6, and get Combining this observation with (i) and (ii) yields the claim.
We are almost prepared to prove Theorem 4.2. As a preparation, the next remark is a collection of statements we did not include in Proposition 4.1 for improved readability, but are important to show the encodability of the weights.
Remark E.2. The neural networks Φ ε,f = ( (A 1 , b 1 ), . . . , (A L−1 , b L−1 ), (A L , b L )) are constructed in such a way that only the weights (A L , b L ) in the last layer depend on the function f . In other words, the weights in the layers 1, . . . , L − 1 are independent from f . They only depend on ε, n, d, p, k, µ. This fact will play a crucial role in proving the encodability of the neural network weights in Theorem 4.2. Additionally, we will use the following fact: Set )] i W k,∞ (0,∞) d ≤ CN k+µ (k=2) ≤ C ε −(k+µ (k=2) )/(n−k−µ (k=2) ) .
The proof of Theorem 4.2 now mainly consists of showing that the conditions from Lemma E.1 are fulfilled and that the weights from the layers 1, . . . , L − 1, which are not rounded, can be encoded by a moderate number of bits.