## Deep ReLU network approximation of functions on a manifold

Johannes Schmidt-Hieber ∗

## Abstract

Whereas recovery of the manifold from data is a well-studied topic, approximation rates for functions defined on manifolds are less known. In this work, we study a regression problem with inputs on a d ∗ -dimensional manifold that is embedded into a space with potentially much larger ambient dimension. It is shown that sparsely connected deep ReLU networks can approximate a H¨lder function with smoothness o index β up to error ε using of the order of ε -d ∗ /β log(1 /ε ) many non-zero network parameters. As an application, we derive statistical convergence rates for the estimator minimizing the empirical risk over all possible choices of bounded network parameters.

Keywords: manifolds; neural networks; ReLU activation function; approximation rates; estimation risk.

## 1 Introduction

Suppose our training data are given by ( X i , Y i ) , i = 1 , . . . , n, with X i ∈ R d the d -dimensional input vectors and Y i ∈ R the corresponding real-valued outputs. For many machine learning applications the inputs will lie in a somehow 'small' subset compared to R d . This is in particular true for image classification problems where the the input consists of vectors of pixel values. Images of cats and dogs for instance are a tiny subset of all images that can be created by arbitrarily assigning each pixel value. Although these subsets are small they cannot be parametrized. A natural way to model the input space, is to assume that the input vectors lie on an unknown d ∗ -dimensional manifold M .

∗ University of Twente, Drienerlolaan 5, 7522 NB Enschede, The Netherlands.

Email: a.j.schmidt-hieber@utwente.nl

The research has been supported by the Dutch STAR network and a Vidi grant from the Dutch science organization (NWO).

The objective of deep learning is to reconstruct the relationship between input and output. If there is no noise in the observations, we can assume that there exists an unknown function f with Y i = f ( X i ) for all i. Training a network on the dataset ( X i , Y i ) i should then return a deep neural network g that is close to f. In this framework we are not interested in the reconstruction of the manifold M .

A naive approach would be to approximate the function f on the whole domain. It is, however, known that in order to achieve approximation error ε for a β -smooth H¨ older function on R d a ReLU network with depth L will need ε -d/β / L ( log(1 /ε )) many nonzero parameters, see Lemma 1 in [26] for a precise statement. If the function is defined on a d ∗ -dimensional manifold O ε ( -d /β ∗ ) many non-zero network parameters should be, however, sufficient (up to logarithmic terms). In this work we give a construction requiring O ε ( -d /β ∗ log(1 /ε )) non-zero parameters. Although the approximation rate is very natural, the proof is involved and requires a notion of smooth local coordinates that is of independent interest.

The mathematical attempts to understand deep learning started only recently and are still at their infancy. Nearly all results up to now require either strong assumptions or even avoid key aspects of deep networks such as depth and non-linearity in the parameter map by considering only shallow architectures and/or linearizations.

Deep learning can be viewed as a statistical method for prediction. To describe for which tasks this method performs well and when it fails is one of the key challenges that has to be answered by any sound theory of deep learning. An important aspect of this problem is to study the approximation theory induced by a deep network. To identify settings in which deep neural networks perform well, a good understanding of the approximation theory might be at least as useful as the analysis of algorithmic aspects.

The most natural concept is to assume smoothness of the target function. Without any additional constraints, smoothness alone will lead to very slow approximation rates in the high dimensional setups for which deep learning still works well. It is therefore important to identify structural constraints for which fast approximation rates can be obtained.

In the statistics literature it has been argued that neural networks perform well if the function that needs to be learned has itself a composition structure, cf. [12, 2, 25, 20, 26]. Since a deep network can be viewed as a composition of simpler functions, this seems to be in a sense the natural structure that can be learned by this method. And indeed, many of the tasks for which deep neural networks are applied successfully have an underlying composition structure, including image classification, text analysis and game playing. For composition structures, optimal estimation rates can be attained by regressing a possibly

large, but sparsely connected deep network to the data. It is also known that wavelet thresholding estimators can only obtain much slower convergence rates ([26], Section 5). The theory is, however, far from being complete, as many unrealistic assumptions have to be imposed.

In this work, we continue this line of work by studying an instance where the target function f that has to be learned can be written for some (unknown) invertible map γ as

$$f = ( f \circ \gamma ^ { - 1 } ) \circ \gamma$$

and f ◦ γ -1 is somehow easier to approximate than f. Since this representation has a composition structure, a deep network should be able to adapt to the structure and to learn γ and f ◦ γ -1 in the first and last layers, respectively. Compared to a method that learns f directly, faster approximation rates and consequently also faster statistical estimation rates should then be obtainable. In the case of function approximation on a d ∗ -dimensional manifold (ignoring for the moment that there are in general several charts), γ is the local coordinate map and if γ -1 is smooth, f ◦ γ -1 has the same smoothness as f but is defined on R d ∗ instead of R d making f ◦ γ -1 easier to approximate due to the well known curse of dimensionality.

Another instance for a decomposition of the form (1.1) is the Kolmogorov-Arnold representation. The KA representation has been viewed as a very specific neural network with two hidden layers. Although its connection to neural networks is still dubious, it is often listed among arguments why additional network layers are favorable. We will provide some additional insights in a companion article.

Approximation theoretic results from the nineties mainly deal with shallow network and results are formulated to hold for large classes of activation functions, see [18] for an example. The proofs typically exploit variations of the fact that if an activation function is smooth in a small neighborhood with non-vanishing derivatives, then all polynomials can be approximated arbitrarily well by a shallow network. Together with bounds on polynomial approximation this lead to approximation error estimates. One can then wonder why one should not work with polynomial approximations directly, see for instance [24], p.177.

For deep networks, the choice of the activation functions matters and the ReLU (rectified linear unit) activation function σ x ( ) = max( x, 0) has been found to outperform other activation functions for classification tasks in terms of misclassification rates and the computational cost, cf. [8]. From an approximation theoretic point of view, it makes therefore sense to study approximation rates for specific activation functions.

In this work, we specifically study ReLU networks and we heavily exploit the properties of the ReLU. One of the important features of the ReLU is the projection property σ ◦ σ = σ,

which means that one can learn skip connections in the network. To illustrate the use of such a skip connection for approximation by deep networks assume that we need to construct several functions simultaneously within one network. In the case of manifold learning, this will be for instance the local coordinate maps and the functions defining a partition of unity. If for some of these functions we need networks with L 1 hidden layers and for the other functions L 2 &lt; L 1 hidden layers are required. By adding identity maps and using that σ ◦ σ = σ, we can then squeeze in additional hidden layers such that all functions can be simultaneously computed by a neural network with L 1 hidden layers. For more precise statements, see also (2.6) and (2.7). One should also observe that for a general continuous activation function the approximation of the identity is difficult, see Proposition 2.9 in [22].

Moreover, we use other ReLU specific network constructions in order to approximate for instance the multiplication of two inputs, see [29, 17, 31]. Existing approximation theoretic results for general activation functions require that the size of the network parameters increases as the approximation error decreases. In practice, however, the network parameters are randomly initialized by small numbers and the trained network weights are typically close to the initialized ones and therefore do not become large. As we consider ReLU networks, we are able to show that good approximation rates are achievable even if all network parameters are bounded in absolute value by one.

Literature on the related problem of reconstructing the manifold from samples includes [3, 27, 11, 1]. For function approximation on manifolds with networks, [19] gives an approximation rate using so called Eignets and [5] provides a survey of the field and proposes a variation of (1.1) for function approximation on manifolds.

For ReLU networks, approximation rates and statistical risk bounds have been obtained for multivariate function approximation under smoothnes constraints [14, 9, 16, 28, 10] and under structural constraints, including compositions of functions [15, 2] and piecewise smooth functions [23, 13]. [6] compares deep ReLU networks and multivariate adaptive regression splines (MARS). While finishing the article, we became aware of the very recently released work by Nakada and Imaizumi [21]. In this article, approximation rates and statistical risk bounds are derived depending on the Minkowski dimension of the domain. While our approach is more inspired by the idea to rewrite the problem as a composition of function, Nakada and Imaizumi use a different proving strategy. In Remark 1, we describe an example where the Minkowski dimension is equal to the ambient dimension but still faster rates can be obtained using the approach described in this article. Another difference is that in our approach all network weights are bounded in absolute value by one, which, as mentioned above, is more in line with practice.

The article is structured as follows. In Section 2, we define deep ReLU network function classes and recall important embedding properties. The network approximation of functions on manifolds is considered in Section 3. This section also contains the definition of manifolds with smooth local coordinate maps and the main approximation error bound. An application to prediction error bounds for the empirical risk minimizer over sparsely connected deep ReLU networks can be found in Section 4. Longer proofs and additional technical lemmas are deferred to the appendix.

glyph[negationslash]

Notation: For a vector x = ( x , . . . , x 1 d ) , | x | p := ( ∑ d i =1 | x i | p ) 1 /p , | x | ∞ := max i | x i | , and | x | 0 := ∑ i 1 ( x i = 0) . For a vector valued function f defined on the domain D, we set ‖ f ‖ L ∞ ( D ) := max x ∈ D | f ( x ) | ∞ .

## 2 Deep feedforward neural networks

Feedforward means that the information is passed in one direction through the network. We can either write a network function via a recursion or via, what is sometimes called, an unfolded representation. For our purposes the unfolded representation turns out to be more convenient and we follow the notation in [26]. Throughout the article, we work with ReLU networks, which means that the activation function σ is taken to be σ x ( ) = max( x, 0) = ( x ) + . For vectors v = ( v , . . . , v 1 r ) glyph[latticetop] , y = ( y , . . . , y 1 r ) glyph[latticetop] ∈ R r , the shifted activation function is defined as σ v = ( σ y ( 1 -v 1 ) , . . . , σ ( y r -v r )) glyph[latticetop] : R r → R r . We also define a separate output activation function ρ : R r → R s that is chosen in dependence on the statistical problem. For regression, ρ is the identity. For classification the softmax

$$\rho ( \mathbf z ) = \left ( \frac { e ^ { z _ { 1 } } } { \sum _ { j = 1 } ^ { r } e ^ { z _ { j } } }, \dots, \frac { e ^ { z _ { r } } } { \sum _ { j = 1 } ^ { r } e ^ { z _ { j } } } \right ) ^ { \top }$$

is used mapping z to a probability vector. The network architecture ( L, p ) consists of a positive integer L called the number of hidden layers or depth and a width vector p = ( p , . . . , p 0 L +1 ) ∈ N L +2 . A neural network with network architecture ( L, p ) is then any function of the form

↦

$$f \, \colon \mathbb { R } ^ { p _ { 0 } } \rightarrow \mathbb { R } ^ { p _ { L + 1 } }, \ \ x \mapsto f ( \mathbf x ) = \rho W _ { L } \sigma _ { \mathbf v _ { L } } W _ { L - 1 } \sigma _ { \mathbf v _ { L - 1 } } \cdots W _ { 1 } \sigma _ { \mathbf v _ { 1 } } W _ { 0 } \mathbf x, \quad \ ( 2. 1 )$$

where W i is a p i × p i +1 weight matrix and v i ∈ R p i is a shift vector. Given a function g and a network architecture ( L, p ) , the approximation problem is to construct a network function of the form (2.1) with small approximation error. This means that L, p are fixed and the adjustable parameters are the entries of the matrices W ,... , W 0 L and the shift vectors v , . . . , v 1 L .

Let ‖ W j ‖ 0 denote the number of non-zero entries of W j and ‖ W j ‖ ∞ the maximum-entry norm of W . j The s -sparse networks with network parameters all bounded in absolute value by one are

$$\mathcal { F } ( L, \mathbf p, s ) \coloneqq \left \{ f \, \text{of the form } ( 2. 1 ) \ \colon \, \max _ { j = 0, \dots, L } \| W _ { j } \| _ { \infty } \vee | \mathbf v _ { j } | _ { \infty } \leq 1, \, \sum _ { j = 0 } ^ { L } \| W _ { j } \| _ { 0 } + | \mathbf v _ { j } | _ { 0 } \leq s \right \},$$

with the convention that v 0 is a vector with coefficients all equal to zero. For fully connected networks, we omit s and write F ( L, p ) . As all the networks that we consider in this work have the same width for all hidden layers and the widths of the hidden layers are most of the time complicated expressions, it is convenient to introduce

$$\mathcal { F } ( L, ( p _ { 0 } \sim p \sim p _ { L + 1 } ), s ) \coloneqq \mathcal { F } ( L, ( p _ { 0 }, \underbrace { p, \dots, p } _ { L \text{ times} }, p _ { L + 1 }, s ).$$

We frequently make use of the fact that for a fully connected network in F ( L, p ) , there are ∑ L glyph[lscript] =0 p p glyph[lscript] glyph[lscript] +1 weight matrix parameters and ∑ L glyph[lscript] =1 p glyph[lscript] network parameters coming from the shift vectors. The total number of parameters is thus

$$\sum _ { \ell = 0 } ^ { L } ( p _ { \ell } + 1 ) p _ { \ell + 1 } - p _ { L + 1 }.$$

To prove approximation error bounds, the general proof strategy is to build first smaller networks and then combine them into one big network. To combine networks, we make frequently use of the following rules. Firstly, network function spaces are enlarged by increasing the width vector and the number of non-zero network entries,

$$\mathcal { F } ( L, \mathbf p, s ) \subseteq \mathcal { F } ( L, \mathbf q, s ^ { \prime } ) \ \text{ whenever } \mathbf p \leq \mathbf q \text{ componentwise and } s \leq s ^ { \prime }. \quad \ ( 2. 4 )$$

We can also compose two networks if the number of units in the output layer of the first network matches the number of units in the input layer of the second network. More concretely, for p = ( p , . . . , p 0 L +1 ) and p ′ = ( p , . . . , p ′ 0 ′ L +1 ) ,

$$f \in & \mathcal { F } ( L, \mathbf p ), \ g \in \mathcal { F } ( L ^ { \prime }, \mathbf p ^ { \prime } ), \ p _ { L + 1 } = p _ { 0 } ^ { \prime }, \ \mathbf v \in [ - 1, 1 ] ^ { p _ { L + 1 } }, \\ & \Rightarrow \ g \circ \sigma _ { \mathbf v } ( f ) \in \mathcal { F } ( L + L ^ { \prime } + 1, ( \mathbf p, p _ { 1 } ^ { \prime }, \dots, p _ { L ^ { \prime } + 1 } ^ { \prime } ) ).$$

To synchronize the number of hidden layers for two networks, we can squeeze in add additional layers with identity weight matrix. Adding the extra hidden layers at the bottom of the network yields the inclusion

$$\mathcal { F } ( L, \mathbf p, s ) \subset \mathcal { F } ( L + q, ( \underbrace { p _ { 0 }, \dots, p _ { 0 } } _ { q \text{ times} }, \mathbf p ), s + q p _ { 0 } ).$$

Moreover, two networks of the same depth can be combined in order to compute two network functions in parallel,

$$f & \in \mathcal { F } ( L, \mathbf p, s ), \ g \in \mathcal { F } ( L, \mathbf p ^ { \prime }, s ^ { \prime } ), \ p _ { 0 } = p _ { 0 } ^ { \prime } \\ & \quad \Rightarrow \ ( f, g ) \in \mathcal { F } ( L, ( p _ { 0 }, p _ { 1 } + p _ { 1 } ^ { \prime }, \dots, p _ { L + 1 } + p _ { L + 1 } ^ { \prime } ), s + s ^ { \prime } ).$$

Finally, for sparse networks having more than s units in one hidden layer does not add anything to the function class and

$$\mathcal { F } ( L, \mathbf p, s ) = \mathcal { F } ( L, ( p _ { 0 }, p _ { 1 } \wedge s, p _ { 2 } \wedge s, \dots, p _ { L } \wedge s, p _ { L + 1 } ), s ).$$

A proof of this fact is given in [26].

## 3 ReLU network approximation of a function on a manifold

As a prerequisite, we need to define H¨lder functions on manifolds. Based on this definition, o we can then introduce compact manifolds with H¨lder smooth local coordinate charts and o derive several properties such as existence of a partition of unity. The main approximation error bound is stated in Theorem 2 at the end of the section.

H¨ older functions and smoothness on a manifold: For an index β ≤ 1 , a function f : D → R , q with D an open set in R r , has H¨ older smoothness index β, if | f ( x ) -f ( y ) | ≤ C | x -y | β . Because of the equivalence of norms on finite dimensional vectors spaces, | · | can be any norm. H¨lder continuity can be extended to o β &gt; 1 . Let glyph[floorleft] β glyph[floorright] denote the largest integer strictly smaller than β. For a real-valued function, the ball of β -H¨ older functions with radius K is then defined as glyph[negationslash]

$$\mathcal { C } _ { r } ^ { \beta } ( D, K ) = \left \{ f \colon D \subset \mathbb { R } ^ { r } \to \mathbb { R } \, \colon \\ \sum _ { \alpha \colon | \alpha | < \beta } \| \partial ^ { \alpha } f \| _ { L ^ { \infty } ( D ) } + \sum _ { \alpha \colon | \alpha | = \lfloor \beta \rfloor } \sup _ { x, y \in D } \frac { | \partial ^ { \alpha } f ( x ) - \partial ^ { \alpha } f ( y ) | } { | x - y | _ { \infty } ^ { \beta - \lfloor \beta \rfloor } } \leq K \right \},$$

where we used multi-index notation, that is, ∂ α = ∂ α 1 . . . ∂ α r with α = ( α , . . . , α 1 r ) ∈ N r and | α | := | α | 1 . For a vector valued function f, we write f ∈ C β r ( D,K ) if all the component functions are in C β r ( D,K . ) This space is sometimes also denoted by C β -glyph[floorleft] β , glyph[floorright] glyph[floorleft] β glyph[floorright] , cf. [7].

For two vectors x ∈ R r and α ∈ N r write x α := x α 1 1 · . . . · x α r r and α ! := α 1 ! · . . . · α r ! . Define P β a f ( x ) = ∑ α α &lt;β : | | ( ∂ α f )( a )( x -a ) α / α ! . If D is also convex and a ∈ D, then, by Taylor's theorem for multivariate functions, there exists ξ ∈ [0 , 1] , such that

$$f ( { \mathbf x } ) = P _ { \mathbf a } ^ { \beta } f ( { \mathbf x } ) + \sum _ { \beta - 1 \leq | \alpha | < \beta } \left ( ( \partial ^ { \alpha } f ) ( { \mathbf a } + \xi ( { \mathbf x } - { \mathbf a } ) ) - ( \partial ^ { \alpha } f ) ( { \mathbf a } ) \right ) \frac { ( { \mathbf x } - { \mathbf a } ) ^ { \alpha } } { \alpha! },$$

and so, for f ∈ C β r ( D,K , )

$$| f ( \mathbf x ) - P _ { \mathbf a } ^ { \beta } f ( \mathbf x ) | & = \sum _ { \beta - 1 \leq | \alpha | < \beta } \frac { | ( \mathbf x - \mathbf a ) ^ { \alpha } | } { \alpha! } | ( \partial ^ { \alpha } f ) ( \mathbf a + \xi ( \mathbf x - \mathbf a ) ) - ( \partial ^ { \alpha } f ) ( \mathbf a ) | \\ & \leq K | \mathbf x - \mathbf a | _ { \infty } ^ { \beta }.$$

This means that a β -H¨ older function can be approximated in the neighborhood of any point a by a polynomial of order glyph[floorleft] β glyph[floorright] up to an approximation error O ( | x - | a β ∞ ) . Via this property, we can define H¨lder functions on any subset of a metric space. o To denote the difference, we use C instead of the calligraphic C and write

$$C _ { r } ^ { \beta } ( D, K ) \coloneqq & \left \{ f \colon D \subset \mathbb { R } ^ { r } \to \mathbb { R } \colon \text{ for any } \mathfrak { a } \in D, \ \exists \ P _ { \mathfrak { a } } ^ { \beta } f ( { \mathbf x } ) = \sum _ { 0 \leq | \gamma | < \beta } c _ { \gamma, \mathfrak { a } } { \mathbf x } ^ { \gamma } \\ & \text{ with } | f ( { \mathbf x } ) - P _ { \mathfrak { a } } ^ { \beta } f ( { \mathbf x } ) | \leq K | { \mathbf x } - \mathfrak { a } | _ { \infty } ^ { \beta }, \ \forall { \mathbf x } \in D, \ \text{ and } \sup _ { \mathfrak { a } \in D, \ 0 \leq \gamma < \beta } \gamma! | c _ { \gamma, \mathfrak { a } } | \leq K \right \}.$$

$$\text{with } \left | f ( \mathbf x ) - P _ { \mathbf a } ^ { \beta } f ( \mathbf x ) \right | \leq K | \mathbf x - \mathbf a | _ { \infty } ^ { \beta }, \ \forall \mathbf x \in D, \text{ and } \sup _ { \mathbf a \in D, \ 0 \leq \gamma < \beta } \gamma! | c _ { \gamma, \mathbf a } | \leq K \right \}.$$

As before, for vector valued functions, f ∈ C β r ( D,K ) means that all component functions are in this space. We also define

$$C _ { r } ^ { \beta } ( D ) \coloneqq \cup _ { K > 0 } C _ { r } ^ { \beta } ( D, K ).$$

If D is a bounded domain, it is not hard to show that C β r ( D ) ⊆ C β ′ r ( D ) whenever β ′ ≤ β. If f ∈ C 1 r ( D,K , ) then, P β a f = f ( a ) and thus f is Lipschitz with Lipschitz constant bounded by K. Together with the embedding property, this shows that f ∈ C β r ( D ) is Lipschitz if β ≥ 1 and D is bounded.

Lemma 1. Let D ⊆ R r be an open set and consider a bounded function f : D → R . Suppose that all partial derivatives of f exist, are bounded and vanish outside of a bounded set. Then, f ∈ C β r ( D ) for all β &gt; 0 .

Proof. Rewriting

$$P _ { \mathbf a } ^ { \beta } f ( \mathbf x ) = \sum _ { \alpha \colon | \alpha | < \beta } \frac { ( \partial ^ { \alpha } f ) ( \mathbf a ) ( \mathbf x - \mathbf a ) ^ { \alpha } } { \alpha! } = \sum _ { 0 \leq | \gamma | < \beta } \mathbf x ^ { \gamma } \sum _ { \gamma \leq \alpha \& | \alpha | < \beta } ( \partial ^ { \alpha } f ) ( \mathbf a ) \frac { ( - \mathbf a ) ^ { \alpha - \gamma } } { \gamma! ( \alpha - \gamma )! },$$

the result follows from (3.1).

Lemma 2. Let D ⊂ R r be a bounded set and β ≥ 1 . If f ∈ C β r ( D ) is a function mapping to R q and g ∈ C β q ( R q ) , then, g ◦ f ∈ C β r ( D . )

The proof is given in the appendix.

Manifolds with smooth local coordinates: We consider a d ∗ -dimensional compact manifold M . By definition of a compact manifold, there exist open sets V , . . . , V 1 r ⊂ M

with ∪ j V j = M and coordinate maps ψ j : R d ∗ → V , j j = 1 , . . . , r. A smooth manifold only guarantees that the transfer functions are smooth. It does not say anything about the smoothness of a local coordinate map or its inverse. We will therefore impose additional structure here.

Definition 1. We say that a compact d ∗ -dimensional manifold M⊂ R d has smooth local coordinates if there exist charts ( V , ψ 1 1 ) , . . . , ( V , ψ r r ) , such that for any γ &gt; 0 , ψ j ∈ C γ d ( V j ) and ψ -1 j ∈ C γ d ∗ ( ψ j ( V j )) for all j = 1 , . . . , r.

↦

As an example consider the unit sphere S 1 ⊂ R 2 . Every point on the sphere can be written as (sin t, cos t ) , 0 ≤ t &lt; 2 π. Defining the charts such that ( x, y ) → arcsin( x ) and ( x, y ) → arccos( y ) are invertible and smooth on the covering, it can be shown that S 1 is a manifold with smooth local coordinates in the sense of Definition 1.

↦

↦

The notion of smooth local coordinates is also compatible with the standard operations to construct more complicated manifolds from simpler ones. If, for instance, M and N are compact manifolds with dimension d ∗ 1 and d , ∗ 2 respectively and smooth local coordinates, then, M×N is a compact d ∗ 1 + d ∗ 2 -dimensional manifold with smooth local coordinates. This can be checked as follows. If ( V , ψ 1 1 ) , . . . , ( V , ψ r r ) are the charts for M and ( W ,φ 1 1 ) , . . . , ( W ,φ r s ) the charts for N , then, one can directly verify the conditions for the charts ( V k × W , glyph[lscript] ( x y , ) → ( ψ k ( x ) , φ glyph[lscript] ( y )) glyph[latticetop] ) , k = 1 , . . . , r, glyph[lscript] = 1 , . . . , s.

Partition of unity: On a compact manifold M , it is always possible to find a finite partition of unity, see Section 13.3 in [30]. As we require additional smoothness and support properties, a more refined result is needed. This leads to several complications in the proof which is deferred to the appendix.

For a vector x and a set A on the same vector space, | x -A | ∞ := inf a ∈ A | x -a | ∞ . For δ &gt; 0 , define

$$V _ { j } ^ { - \delta } \coloneqq \{ \mathbf y \in V _ { j } \, \colon | \mathbf y - ( \mathcal { M } \, \sum V _ { j } ) | _ { \infty } \geq \delta \}.$$

Lemma 3. Consider a compact d ∗ -dimensional manifold M⊂ R d with smooth local coordinates. Then, there exist a δ &gt; 0 and non-negative functions τ j : M→ R , j = 1 , . . . , r, such that for any γ &gt; 0 , and any x ∈ M { , y ∈ M : τ j ( y ) &gt; 0 } ⊆ V -δ j , τ j ∈ C γ d ( M ) , and ∑ r j =1 τ j ( x ) = 1 .

Main idea for construction of network approximation: The strategy is to build a deep neural network with good approximation properties combining simpler networks approximating ψ , f j ◦ ψ -1 j , and τ , j j = 1 , . . . , r. Combining the single networks we can then

Figure 1: Combining smaller networks to build an approximation of the functions ˜ τ j ( x ) · ( ˜ f ◦ ψ -1 j ) ◦ ˜ ψ j ( x ). Here, ⊗ stands for the multiplication network introduced in Lemma 4.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00695v1-figure-f8610684-9b46-441d-8944-12ca0f9d00f5.jpg)

construct a deep ReLU network mimicking the left hand side in the identity

$$\sum _ { j = 1 } ^ { K } \tau _ { j } ( { \mathbf x } ) \left ( f \circ \psi _ { j } ^ { - 1 } \right ) \circ \psi _ { j } ( { \mathbf x } ) = f ( { \mathbf x } ), \quad \text{for all } { \mathbf x } \in \mathcal { M }$$

where each summand is defined as zero if τ j ( x ) = 0 . The main steps of the network construction are also summarized in Figure 1.

## Approximations of H¨lder functions by deep ReLU networks: o

Theorem 1. Suppose that U ⊂ R d is a bounded set. For any function g : U → R d ′ in the H¨ older space g ∈ C β d ( U, K ) and any integers m ≥ 1 and N ≥ 5 d ∨ ( β + 1) d ∨ ( K + 1) e , d there exists a network

$$\widetilde { g } \in \mathcal { F } \left ( L, \left ( d \sim 6 d ^ { \prime } ( d + \lceil \beta \rceil ) N \sim d ^ { \prime } \right ), s \right )$$

with depth

$$L = 9 + ( m + 5 ) ( 1 + \lceil \log _ { 2 } ( d \vee \beta ) \rceil )$$

and number of parameters

$$s \leq 1 4 2 d ^ { \prime } ( d + \beta + 1 ) ^ { 3 + d } N ( m + 6 ),$$

such that with R := 1 ∨ 4 max x ∈ U | x | ∞ ,

$$\| \widetilde { g } - g \| _ { L ^ { \infty } ( U ) } \leq ( 2 K R ^ { \beta } + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + K ( 9 R ) ^ { \beta } N ^ { - \frac { \beta } { d } }.$$

The upper bound for the approximation error consists of two terms. Since we have s glyph[equivasymptotic] Nm parameters we expect the well-known approximation rate ( Nm ) -β/r . The second term coincides with this rate up to the factor m. This suggests to choose m small. Then, however, the first term in the bound of the approximation error will become large. The optimal tradeoff is (1 + β/d ) log 2 ( N ) ≤ m glyph[lessorsimilar] log( N ) in which case approximation error O N ( -β d ) can be achieved for O N ( log N ) non-zero network parameters.

The proof of Theorem 1 builds on Theorem 5 in [26] constructing a deep ReLU network ˜ f from simpler networks that compute a linear combination of local Taylor approximations of f. More precisely, U is rescaled to fit into the hypercube [0 , 1] d and then a uniform grid on this hypercube is constructed. On each of the grid points, we construct a sub-network approximating a glyph[floorleft] β glyph[floorright] -th order Taylor approximation at that point, where as before, glyph[floorleft] β glyph[floorright] denotes the largest integer strictly smaller than β. The function reconstruction at a specific point is then a weighted sum of the Taylor approximation at the surrounding points. There are several technical issues that occur, for instance, for a point close to the boundary, some of the surrounding grid points lie outside the rescaled version of the set U and the glyph[floorleft] β glyph[floorright] -th order Taylor approximation on these points is not well defined.

Main approximation error bound: Following the strategy outlined in Figure 1 to construct a network mimicking the left hand side in (3.2), we are now able to state the main result of the article.

Theorem 2. Let M⊂ R d be a compact d ∗ -dimensional manifold with smooth local coordinates. Then, there exist positive constants c, C, C , ′ such that for any 0 &lt; η ≤ 1 2 / , any c log(1 /η ) ≤ L, any p &gt; Cη -d /β ∗ and any s ≥ C Lη ′ -d /β ∗ ,

$$\sup _ { f \colon \mathbb { R } ^ { d } \to [ - 1, 1 ], \ f \in \mathcal { C } _ { d } ^ { \beta } ( \mathbb { R } ^ { d }, K ) } \inf _ { \widetilde { f } \in \mathcal { F } ( L, ( d \sim p \sim 1 ), s ) } \| \widetilde { f } - f \| _ { L ^ { \infty } ( \mathcal { M } ) } \leq \eta.$$

The proof allows to exactly quantify the dependence of the constants c, C, and C , ′ on d, d ∗ , β, K. This, however, leads to complicated expressions.

Remark 1. The approach using (3.2) can be easily extended if there is additional invariance in the function f. To illustrate this, suppose that M⊂ R d 1 is a compact d ∗ -dimensional manifold with smooth local coordinates in the sense of Definition 1. Denote the charts of M by ( V , ψ 1 1 ) , . . . , ( V , ψ r r ) and the functions forming a partition of unity by τ , . . . , τ 1 r . Let U ⊂ R d 2 be a compact set containing the vector (0 , . . . , 0) glyph[latticetop] . Suppose now that we want to approximate f : R d → R with d = d 1 + d 2 on the set M× U. Assume moreover that f is independent of the last components in the vector in the sense that f ( x , . . . , x 1 d ) = f ( x , . . . , x 1 d 1 ) .

Defining ψ j ( x , . . . , x 1 d ) := ψ x , . . . , x ( 1 d 1 ) and τ j ( x , . . . , x 1 d ) := τ ( x , . . . , x 1 d 1 ) , we now have

$$\sum _ { j = 1 } ^ { K } \bar { \tau } _ { j } ( { \mathbf x } ) \left ( f \circ \psi _ { j } ^ { - 1 } \right ) \circ \overline { \psi } _ { j } ( { \mathbf x } ) = f ( { \mathbf x } ), \quad f o r \ a l l \ { \mathbf x } \in \mathcal { M } \times U.$$

If f ∈ C β d ( R d ) , it is clear that O Lη ( -d /β ∗ ) network parameters are needed to approximate f on M× U up to sup-norm error η. To obtain this rate, we only need to know d ∗ and β but not what the invariance property of f is. One should also observe that the Minkowski dimension of the set M× U is d if U is for instance a ball. This means that if the approach in [21] is followed without modification, O Lη ( -d/β ) many non-zero network parameters are needed, which can be considerably larger if d glyph[greatermuch] d . ∗

## 4 Statistical risk bounds

In this section, we convert the approximation error bounds in statistical risk estimates. Suppose we observe n identically distributed pairs ( X i , Y i ) ∈ R d × R with

$$Y _ { i } = f _ { 0 } ( \mathbf X _ { i } ) + \varepsilon _ { i }, \ \ i = 1, \dots, n,$$

and ( ε i ) i a sequence of i.i.d. standard normal measurement errors that are independent of the design vectors X i . As before, the X i are assumed to lie on a compact d ∗ -dimensional manifold M with smooth local coordinates. The manifold M is unknown and we also suppose that M⊆ [0 , 1] d . We moreover assume that f 0 ∈ C β d ( R d ) for some β and ‖ f 0 ‖ L ∞ ( R d ) ≤ 1 .

In statistics, a lot of research has been devoted to approximation bounds and statistical risk bound under shape constraints on the regression function f . 0 But relatively little is known for constraints on the design. An exception is [4], studying locally polynomial estimators in nonparametric regression with design on an unknown manifold.

The prediction risk is the expected loss that we suffer by predicting the output for a new input vector that is generated from the same distribution as the design vectors in the training set. Thus, with X D = X 1 being independent of the sample ( X i , Y i ) i , the prediction risk is given by

$$R ( \widehat { f } _ { n }, f _ { 0 } ) \coloneqq E _ { f _ { 0 } } \left [ \left ( \widehat { f } _ { n } ( \mathbf X ) - f _ { 0 } ( \mathbf X ) \right ) ^ { 2 } \right ],$$

where E f 0 denotes the expectation over X and independent ( X i , Y i ) i =1 ,...,n generated from model (4.1).

We study the empirical risk estimator (ERM) over the class F ( L, p , s ) ∩ { f : [0 , 1] d → [ -1 1] , } , that is,

$$\widehat { f } _ { n } \in \underset { f \in \mathcal { F } ( L, \mathbf p, s ) \cap \{ f \colon [ 0, 1 ] ^ { d } \to [ - 1, 1 ] \} } { \arg \min } \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left ( Y _ { i } - f ( \mathbf X _ { i } ) \right ) ^ { 2 }.$$

To compute the ERM is extremely hard if not infeasible for non-convex function spaces such as neural networks. On the contrary, via empirical processes, theoretical guarantees can be obtained. Therefore, we restrict ourselves here to the ERM analysis and refer to [26] for an extension. By Lemma 4, Lemma 5 in [26] and (2.8), we have that the prediction risk of the empirical risk minimizer is bounded by

$$R ( \widehat { f } _ { n }, f _ { 0 } ) \leq C \left [ \inf _ { f \in \mathcal { F } } E [ \left ( f ( \mathbf X ) - f _ { 0 } ( \mathbf X ) \right ) ^ { 2 } ] + \frac { ( s + 1 ) \log ( 4 n ( L + 1 ) ( s + 1 ) ^ { L } ( d + 1 ) ) + 1 } { n } \right ],$$

with C a universal constant, F = F ( L, p , s ) ∩{ f : [0 , 1] d → -[ 1 1] , } and E the expectation taken over X . Inequalities of this form are also called oracle inequalities as the statistical risk of the estimator is bounded by the best risk of any element in the class plus some extra term that penalizes the model complexity. The next result is now a straightforward consequence of the abstract risk bound for the empirical risk minimizer in (4.3) and Theorem 2.

Theorem 3. Consider model (4.1) with design on a d ∗ -dimensional compact manifold M⊂ [0 , 1] d and regression function f : R d → -[ 1 1] , in C β d ( R d , K ) . Let ̂ f n be the ERM in (4.2) . Then, there exist constants c, Q &gt; 0 that are independent of n, such that if

$$( i ) & \ c \log n \leq L, \\ ( i i i ) & \ n ^ { d ^ { * } / ( 2 \beta + d ^ { * } ) } \lesssim p, \\ ( i v ) & \ s \asymp L n ^ { d ^ { * } / ( 2 \beta + d ^ { * } ) },$$

then,

$$R ( \widehat { f } _ { n }, f _ { 0 } ) \leq Q n ^ { - \frac { 2 \beta } { 2 \beta + d ^ { * } } } L ^ { 2 } \log ( n ).$$

In particular, L can be chosen of order log( n ) such that the risk is bounded by

$$\text{constant} \times n ^ { - \frac { 2 \beta } { 2 \beta + d ^ { * } } } \log ^ { 3 } ( n ).$$

Proof. Choose η = Rn -2 β 2 β + d ∗ for a sufficiently large constant R, such that, if C and C ′ are as in Theorem 2, p &gt; Cη -d /β ∗ and s ≥ C Lη ′ -d /β ∗ . The result follows from Theorem 2 and (4.3).

## 5 Proofs

Proof of Lemma 2. It is enough to consider the case that g : R q → R . By definition of f ∈ C β r ( D , ) there exists an q -dimensional vector P β a f containing polynomials of degree glyph[floorleft] β , glyph[floorright] and a positive K, such that | f ( x ) -P β a f ( x ) | ∞ ≤ K | x - | a β ∞ , ∀ x a , ∈ D. The coefficients of P β a f are uniformly bounded over a ∈ D. In the same way g ∈ C β q ( R q ) implies existence of a polynomial Q g β u with uniformly bounded coefficients over u ∈ R q approximating g ( y ) up to an error K | y -u | β ∞ for all y u , ∈ R q .

The composition R β a ( x ) := Q β f ( a ) g P ( β a f ( x )) is a polynomial in a -x of degree 2 glyph[floorleft] β . glyph[floorright] Denote by ˜ R β a ( x ) the polynomial obtained by removing in R β a ( x ) all terms ( x -a ) γ with degree | γ | ≥ β. Consequently, ˜ R β a ( x ) is a polynomial of degree glyph[floorleft] β . glyph[floorright]

Th coefficient of ˜ R β a ( x ) are uniformly bounded over a . It remains to show that ˜ R β a ( x ) approximates f ◦ g up to an error constant ×| x -a | β ∞ . Since D is a bounded domain, we conclude that | ˜ R β a ( x ) -R β a ( x ) | ≤ K ′ | x - | a β ∞ for some finite constant K . ′ We must have that B := ∪ a P β a f ( D ) ∪ f ( D ) is a bounded subset of R q . Moreover, since Q β f ( a ) g is a polynomial, it is Lipschitz on B and a Lipschitz constant can be chosen independent of a ∈ D. Similarly, one can show that for sufficiently large K , ′′ max a ∈ D | P β a f ( x ) -P β a f ( y ) | ≤ K ′′ | x -y | ∞ for all x y , ∈ D. Because of β ≥ 1 also f is Lipschitz. Thus, there exists a constant C such that

$$| R _ { \mathbf a } ^ { \beta } ( \mathbf x ) - g \circ f ( \mathbf x ) | & \leq | Q _ { f ( \mathbf a ) } ^ { \beta } g ( P _ { \mathbf a } ^ { \beta } f ( \mathbf x ) ) - Q _ { f ( \mathbf a ) } ^ { \beta } g ( f ( \mathbf x ) ) | + | Q _ { f ( \mathbf a ) } ^ { \beta } g ( f ( \mathbf x ) ) - g \circ f ( \mathbf x ) | \\ & \leq C | P _ { \mathbf a } ^ { \beta } f ( \mathbf x ) - f ( \mathbf x ) | _ { \infty } + C | f ( \mathbf a ) - f ( \mathbf x ) | _ { \infty } ^ { \beta } \\ & \leq C K | \mathbf a - \mathbf x | _ { \infty } ^ { \beta } + C | \mathbf a - \mathbf x | _ { \infty } ^ { \beta },$$

completing the proof for (i).

Proof of Lemma 3. Since M\ V j is a closed set, we have that δ ( x ) := | x - M\ ( V j ) | ∞ := inf y ∈M\ V j | x - | y ∞ &gt; 0 implying that B ∞ δ ( x ) / 2 ( x ) ∩M⊂ V j where B ∞ ε ( x ) = { y : | y - | x ∞ ≤ ε } denotes the | · | ∞ -norm ball around x with radius ε.

Thus, for any j = 1 , . . . , r and any x ∈ V j it is possible to construct a smooth and non-negative function λ x : R d ∗ → [0 , ∞ ) such that ψ j ( x ) ∈ { y ∈ R d ∗ : λ x ( y ) &gt; 0 } ⊆ ψ j ( B ∞ δ ( x ) / 2 ( x ) ∩ M ) and for any β &gt; 0 , λ x ∈ C β d ∗ ( R d ∗ ) . By construction

$$\bigcup _ { j = 1, \dots, r } \bigcup _ { \mathbf x \in V _ { j } } \psi _ { j } ^ { - 1 } \Big ( \left \{ y \in \mathbb { R } ^ { d ^ { * } } \, \colon \lambda _ { \mathbf x } ( y ) > 0 \right \} \Big ) = \mathcal { M }.$$

This is a union over open sets and since M is compact, we can select points x glyph[lscript] ∈ ψ s glyph[lscript] ( ) ( V s glyph[lscript] ( ) ) for glyph[lscript] = 1 , . . . , m and some finite m, where s : { 1 , . . . , m } → { 1 , . . . , r } maps the points x glyph[lscript]

to the corresponding charts, such that

$$\bigcup _ { \ell = 1, \dots, m } \psi _ { s ( \ell ) } ^ { - 1 } \left ( \left \{ \mathbf y \in \mathbb { R } ^ { d ^ { * } } \, \colon \lambda _ { \mathbf x _ { \ell } } ( \mathbf y ) > 0 \right \} \right ) = \mathcal { M }.$$

For j = 1 , . . . , r, define ν j = ∑ glyph[lscript] ∈ s -1 ( j ) λ x glyph[lscript] . Then, ∪ j =1 ,...,r ψ -1 j ( { x ∈ R d ∗ : ν j ( x ) &gt; 0 ) = } M . In a next step, define σ j : M→ [0 , ∞ ) via

$$\sigma _ { j } ( { \mathbf x } ) = \begin{cases} \nu _ { j } \circ \psi _ { j } ( { \mathbf x } ), & \text{if ${\mathbf x}\in V_{j}$}, \\ 0 & \text{otherwise}. \end{cases}$$

By definition of the maps λ , x we have that

$$\inf \left \{ | \mathbf u - \mathbf v | _ { \infty } \, \colon \mathbf u \in \{ \mathbf y \, \colon \sigma _ { j } ( \mathbf y ) > 0 \}, \mathbf v \in \mathcal { M } \, \sum V _ { j } \right \} \geq \min _ { \ell = 1, \dots, m } \frac { \delta ( \mathbf x _ { \ell } ) } { 2 } = \colon \underline { \delta } > 0.$$

By Lemma 2, we have that for any β ≥ 1 , σ j ∈ C β d ( V j ) . We now show that this can be extended such that for any β ≥ 1 , σ j ∈ C β d ( M ) . The property σ j ∈ C β d ( V j ) ensures existence of a polynomial P β a σ j of degree glyph[floorleft] β glyph[floorright] with bounded coefficients where the bound is independent of a . Choose

$$Q _ { \mathbf a } ^ { \beta } \sigma _ { j } \coloneqq \begin{cases} P _ { \mathbf a } ^ { \beta } \sigma _ { j }, & \text{if $|\mathbf a - (\mathcal{M} \, \sum V_{j})|_{\infty} > \underline{d}/2$,} \\ 0 & \text{otherwise.} \end{cases}$$

Obviously, also for the polynomials Q σ , β a j all coefficients can be uniformly bounded over a . To show that | Q σ β a j ( x ) -σ j ( x ) | / | a -x | β ∞ is bounded, we have to consider several cases. Assume first that x ∈ V j and | a - M \ ( V j ) | ∞ &gt; δ/ . 2 Since σ j ∈ C β d ( V j ) , | Q σ β a j ( x ) -σ j ( x ) | / | a - | x β ∞ is bounded. If x ∈ M\ V , j and | a - M\ ( V j ) | ∞ &gt; δ/ , 2 then, δ/ 2 ≤ | x - | a ∞ , and

$$| Q _ { \mathbf a } ^ { \beta } \sigma _ { j } ( \mathbf x ) - \sigma _ { j } ( \mathbf x ) | = | Q _ { \mathbf a } ^ { \beta } \sigma _ { j } ( \mathbf x ) | \leq \sup _ { \mathbf u \in V _ { j } } \| Q _ { \mathbf u } ^ { \beta } \sigma _ { j } \| _ { L ^ { \infty } ( \mathcal { M } ) } \binom { 2 } { \underline { \delta } } ^ { \beta } | \mathbf x - \mathbf a | _ { \infty } ^ { \beta }.$$

If now | a - M\ ( V j ) | ∞ ≤ δ/ 2 and | x - M\ ( V j ) | ∞ &lt; δ, then, | Q σ β a j ( x ) -σ j ( x ) | = 0 | - | 0 = 0 . Finally for the case | a - M\ ( V j ) | ∞ ≤ δ/ 2 and | x - M\ ( V j ) | ∞ ≥ δ, it follows that | x - | ≥ a δ/ 2 and | Q σ β a j ( x ) -σ j ( x ) | ≤ ‖ σ j ‖ L ∞ ( M ) ≤ ‖ σ j ‖ L ∞ ( M ) (2 /δ ) β | x -a | β ∞ . This shows that there exists a constant K ′ such that for all a x , ∈ M | , Q σ β a j ( x ) -σ j ( x ) | ≤ K ′ | a -x | β ∞ , implying that also σ j ∈ C β d ( M ) .

↦

For x ∈ V , j we have σ j ( x ) = ν j ◦ ψ j ( x ) and therefore σ j ( x ) &gt; 0 if x ∈ ψ -1 j ( { y ∈ R d ∗ : ν j ( y ) &gt; 0 ) } . Hence, ∑ r j =1 σ j ( x ) &gt; 0 for all x ∈ M . Since x → ∑ r j =1 σ j ( x ) is continuous and M is compact, also 0 &lt; σ := inf x ∈M ∑ r j =1 σ j ( x ) ≤ sup x ∈M ∑ r j =1 σ j ( x ) =: σ &lt; ∞ .

Choose now G : R 2 → R such that G u,v ( ) = u/v for all σ ≤ u, v ≤ σ, G vanishes outside a bounded set and all partial derivatives of G exist. This can be achieved for instance by choosing a smooth function K with K x ( ) = 0 for all x ≤ 1 4 and / K x ( ) = 1 for all x ≥ 3 4 / and defining G u,v ( ) := K uσ K vσ K σ ( ) ( ) ( +1 -u K σ ) ( +1 -v u/v. ) By Lemma 1, it then follows that G ∈ C β 2 ( R 2 ) for all β &gt; 0 . Since ( σ , j ∑ r glyph[lscript] =1 σ glyph[lscript] ) ∈ C β d ( M ) , we can conclude by Lemma 2 that τ j := G σ , ( j ∑ r glyph[lscript] =1 σ glyph[lscript] ) ∈ C β d ( M ) . This completes the proof.

Proof of Theorem 1. Using the parallelization property (2.7), it is enough to show the result for d ′ = 1 . In this case, the statement is a modification of Theorem 5 in [26]. The theorem states that if for any function f ∈ C β d ([0 , 1] d , K ) and any integers m ≥ 1 and N ≥ ( β + 1) d ∨ ( K +1) e , d there exists a network ˜ f ∈ F ( L, ( d ∼ 6( d + glyph[ceilingleft] β glyph[ceilingright] ) N ∼ 1 ) , s ) with depth

$$L = 8 + ( m + 5 ) ( 1 + \lceil \log _ { 2 } ( d \vee \beta ) \rceil )$$

and number of parameters s ≤ 141( d + β +1) 3+ d N m ( +6) such that ,

$$\| \widetilde { f } - f \| _ { L ^ { \infty } ( [ 0, 1 ] ^ { d } ) } \leq ( 2 K + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + K 3 ^ { \beta } N ^ { - \frac { \beta } { d } }.$$

The remaining proof is split into two parts. In part ( I ) , we show that if U ⊂ [1 / , 4 3 / 4] d , then, for any function g ∈ C β d ( U, K ) and any integers m ≥ 1 and N ≥ 5 d ∨ ( β +1) d ∨ ( K +1) e , d there exists a network ˜ g ∈ F ( L, ( d ∼ 6( d + glyph[ceilingleft] β glyph[ceilingright] ) N ∼ 1 ) , s ) with depth L = 8 + ( m +5)(1+ glyph[ceilingleft] log 2 ( d ∨ β ) glyph[ceilingright] ) and number of parameters s ≤ 141( d + β +1) 3+ d N m ( +6) such that ,

$$\| \widetilde { g } - g \| _ { L ^ { \infty } ( U ) } \leq ( 2 K + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + K 3 ^ { 2 \beta } N ^ { - \frac { \beta } { d } }.$$

In part ( II ) of the proof, we discuss the general case.

Part (I): As the proof follows from a modification of the proof for Theorem in [26], we only describe the differences using the notation in that article. The strategy in that paper is to define the set of grid points D ( M ) := { x glyph[lscript] = ( glyph[lscript] j /M ) j =1 ,...,r : glyph[lscript] = ( glyph[lscript] 1 , . . . , glyph[lscript] r ) ∈ { 0 1 , , . . . , M } } r and to build a network that approximates the glyph[floorleft] β glyph[floorright] -th order Taylor polynomial on each of this grid points. Denote by P β x glyph[lscript] g ( x ) the glyph[floorleft] β glyph[floorright] -th order Taylor polynomial around x glyph[lscript] . Recall that g is a H¨ older function defined on U ⊂ [1 / , 4 3 / 4] d . Thus, P β x glyph[lscript] g ( x ) only exists if x glyph[lscript] ∈ U. If x glyph[lscript] ∈ [0 , 1] d \ U, there exists a (not necessarily unique) grid point z ∗ ∈ arg min z ∈ U ∩ D ( M ) | x glyph[lscript] - | z ∞ . We then set P β x glyph[lscript] g ( x ) := P β z ∗ g ( x ) and define

$$P ^ { \beta } g ( { \mathbf x } ) \coloneqq \sum _ { { \mathbf x } _ { \ell } \in { \mathbf D } ( M ) } P ^ { \beta } _ { { \mathbf x } _ { \ell } } g ( { \mathbf x } ) \prod _ { j = 1 } ^ { r } ( 1 - M | x _ { j } - x _ { j } ^ { \ell } | ) _ { + }.$$

By adapting Lemma B.1 in [26], we have for 1 /M ≤ 1 4 and for any / x ∈ U,

$$\mu _ { \cdot } \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \\ \left | P ^ { \beta } g ( { \mathbf x } ) - g ( { \mathbf x } ) \right | & \leq \max _ { { \mathbf x } _ { \ell } \in \mathbf D ( M ) \colon | { \mathbf x } - { \mathbf x } _ { \ell } | \infty \leq 1 / M } \left | P ^ { \beta } _ { { \mathbf x } _ { \ell } } g ( { \mathbf x } ) - g ( { \mathbf x } ) \right | \\ & \leq \max _ { { \mathbf z } \in U \colon | { \mathbf x } - { \mathbf z } | \infty \leq 3 / M } \left | P ^ { \beta } _ { { \mathbf z } } g ( { \mathbf x } ) - g ( { \mathbf x } ) \right | \\ & \leq K 3 ^ { \beta } M ^ { - \beta }.$$

In Theorem 5 of [26], we can modify the network Q 1 such that for x glyph[lscript] ∈ D ( M , ) (36) still holds, that is,

$$\left | Q _ { 1 } ( { \mathbf x } ) - \left ( \frac { P _ { \mathbf x } ^ { \beta } g ( { \mathbf x } ) } { B } + \frac { 1 } { 2 } \right ) _ { { \mathbf x } _ { \ell } \in { \mathbf D } ( M ) } \right | _ { \infty } \leq \beta ^ { 2 } 2 ^ { - m }.$$

One should notice that all network parameters can be chosen to be bounded in absolute value by one and the construction does not require to enlarge the network architecture. To conclude the proof, one has to apply (5.1) which means that K in the original bound has to be replaced by K 3 β in the step where Lemma B.1 is applied. Together with ( M +1) d ≤ N and M ≥ 4 , the additional requirement N ≥ 5 d occurs.

Part (II): Introduce the affine transformation T : R d → R d , T x = R -1 x +(1 2 / , . . . , 1 2) / glyph[latticetop] . Define U ′ = T U ( ) and observe that U ′ ⊆ [1 / , 4 3 / 4] d . It is straightforward to see that if g ∈ C β d ( U, K , ) then, h := g T ( -1 · ) ∈ C β d ( U , R ′ β K . ) We can now apply the result from the first part, with U replaced by U ′ and K replaced by R K. β This shows that for any integers m ≥ 1 and N ≥ 5 d ∨ ( β +1) d ∨ ( K +1) e , d there exists a network ˜ h ∈ F ( L, ( d ∼ 6( d + glyph[ceilingleft] β glyph[ceilingright] ) N ∼ 1 ) , s ) with depth L = 8+( m +5)(1+ log ( glyph[ceilingleft] 2 d ∨ β ) glyph[ceilingright] ) and number of parameters s ≤ 141( d + β +1) 3+ d N m ( +6) such that ,

$$\| \widetilde { h } - h \| _ { L ^ { \infty } ( U ^ { \prime } ) } \leq ( 2 R ^ { \beta } K + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + R ^ { \beta } K 3 ^ { 2 \beta } N ^ { - \frac { \beta } { d } }.$$

We now define the neural network ˜ g = ˜ h ◦ σ T ( · ) . Since T is an affine transformation, this can be realized by adding one hidden layer to the network architecture of ˜ h. It also adds 2 d non-zero parameters. Since T U ( ) ⊆ [0 , 1] d , we have ˜ g ( x ) = ˜ h T ( x ) for all x ∈ U. Together this shows that for any integers m ≥ 1 and N ≥ 5 d ∨ ( β +1) d ∨ ( K +1) e , d there exists a network ˜ h ∈ F ( L, ( d ∼ 6( d + glyph[ceilingleft] β glyph[ceilingright] ) N ∼ 1 ) , s ) with depth L = 9+( m +5)(1+ glyph[ceilingleft] log 2 ( d ∨ β ) glyph[ceilingright] ) and number of parameters s ≤ 142( d + β +1) 3+ d N m ( +6) such that ,

$$\| \widetilde { g } - g \| _ { L ^ { \infty } ( U ) } \leq \| \widetilde { h } - h \| _ { L ^ { \infty } ( U ^ { \prime } ) } \leq ( 2 R ^ { \beta } K + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + R ^ { \beta } K 3 ^ { 2 \beta } N ^ { - \frac { \beta } { d } }.$$

$$\| \widetilde { g } - g \| _ { L ^ { \infty } ( U ) } \leq \| \tilde { h } - h \| _ { L ^ { \infty } ( U ^ { \prime } ) } \leq ( 2 R ^ { \beta } K + 1 ) ( 1 + d ^ { 2 } + \beta ^ { 2 } ) 6 ^ { d } N 2 ^ { - m } + R ^ { \beta } K 3 ^ { 2 \beta } N ^ { - \frac { \gamma } { d } }.$$

Lemma 4 (Lemma (A.1) in [26]) . For any positive integer m, there exists a network Mult m ∈ F ( m +4 (2 , ∼ 6 ∼ 1)) , such that Mult m ( x, y ) ∈ [0 , 1] ,

$$\left | \text{ Multi} _ { m } ( x, y ) - x y \right | \leq 2 ^ { - m }, \ \text{ for all } x, y \in [ 0, 1 ],$$

and Mult m (0 , y ) = Mult( x, 0) = 0 .

Lemma 5. If ψ -1 j ∈ C 1 d ∗ ( ψ j ( V j )) , ψ j ∈ C 1 d ( V j ) , then, for any δ &gt; 0 , there exists a δ ′ &gt; 0 , such that

$$\left ( \psi _ { j } ( V _ { j } ^ { - \delta } ) \right ) ^ { \delta ^ { \prime } } \coloneqq \left \{ \mathbf y \in \mathbb { R } ^ { d ^ { * } } \, \colon \left | \mathbf y - \psi _ { j } ( V _ { j } ^ { - \delta } ) \right | _ { \infty } \leq \delta ^ { \prime } \right \} \subseteq \psi _ { j } ( V _ { j } ), \ \ \text{ for all } j = 1, \dots, r.$$

Proof. Recall that if f ∈ C 1 r ( U ) with U bounded, then f is Lipschitz. Since V j ⊂ M and M is compact, V j is a bounded set. Together with ψ j ∈ C 1 d ( V j ) , this shows that ψ j ( V j ) is a bounded set and therefore also ψ -1 j is Lipschitz on ψ j ( V j ) . Thus, there exists a constant L such that | ψ -1 j ( u ) -ψ -1 j ( v ) | ∞ ≤ L | u -v | ∞ . This also implies that | ψ j ( x ) -ψ j ( y ) | ∞ ≥ L -1 | x -y | ∞ for all x y , ∈ V . j

↦

For any u ∈ ψ j ( V j ) \ ψ j ( V -δ/ 2 j ) and v ∈ ψ j ( V -δ j ) we have that | v -u | ∞ ≥ δ/ (2 L ) =: R. Suppose that there exist points w / ψ ∈ j ( V j ) and v ∈ ψ j ( V -δ j ) with | w -v | ∞ ≤ R/ . 2 The set of points on the line [0 , 1] glyph[owner] t → t w + (1 -t ) v intersected with ψ j ( V j ) \ ψ j ( V -δ/ 2 j ) cannot be empty and each such element must have a smaller | · | ∞ -norm than R/ 2 which is a contradiction. This shows that w ∈ ψ j ( V j ) and yields the result for δ ′ = R/ 2 &gt; . 0

Lemma 6. Let K,ε &gt; 0 , and assume that h , h 0 ˜ 0 : U ⊂ R p → V ⊂ R q such that ‖ h 0 -˜ h 0 ‖ L ∞ ( U ) ≤ ε. Let V ε := { x ∈ R q : | x -V | ∞ ≤ ε } . If ˜ h 1 : V ε → -[ K,K ] and h 1 ∈ C β d ∗ ( V ε , K ) , then,

$$\left \| h _ { 1 } \circ h _ { 0 } - \widetilde { h } _ { 1 } \circ \widetilde { h } _ { 0 } \right \| _ { L ^ { \infty } ( U ) } \leq K \| h _ { 0 } - \widetilde { h } _ { 0 } \| _ { L ^ { \infty } ( U ) } ^ { \beta \wedge 1 } + \left \| h _ { 1 } - \widetilde { h } _ { 1 } \right \| _ { L ^ { \infty } ( V ^ { \varepsilon } ) }.$$

Proof. The inequality follows from ‖ h 1 ◦ h 0 -˜ h 1 ◦ ˜ h 0 ‖ L ∞ ( U ) ≤ ‖ h 1 ◦ h 0 -h 1 ◦ ˜ ∥ h 0 ∥ L ∞ ( U ) + ‖ h 1 ◦ ˜ h 0 -˜ h 1 ◦ ˜ ∥ h 0 ∥ L ∞ ( U ) and h 1 ∈ C β d ∗ ( V ε , K ) .

Proof of Theorem 2. We use the same notation as before and denote by ( V , ψ 1 1 ) , . . . ( V , ψ r r ) the charts. Since ψ j ∈ C 1 d ( V j ) , ψ j is Lipschitz and ψ j ( V j ) is a bounded set. As we can always add a vector to the local coordinate map ψ j without changing the properties, we can (and will) assume that ψ j ( V j ) ⊂ [1 , ∞ ) d ∗ .

By Lemma 3, there exist δ &gt; 0 and non-negative functions τ j : M→ R , j = 1 , . . . , r, such that for any γ &gt; 0 , and any x ∈ M { , y ∈ M : τ j ( y ) &gt; 0 } ⊆ V -δ j , τ j ∈ C γ d ( M ) , and ∑ r j =1 τ j ( x ) = 1 .

We first show how to build networks approximating the coordinate maps ψ , j the functions f ◦ ψ -1 j and the functions τ . j We then merge these networks into a bigger network imitating the left hand side in (3.2), see also the schematic representation of the construction in Figure 1.

By Definition 1, ψ j ∈ C γ 1 d ( V j ) , where γ 1 := ( β ∨ 1) d/d . ∗ To construct a neural network approximating ψ j on V , j we apply Theorem 1. There exist positive constants C 1 := C 1 ( d, d ∗ , β, j, V j , δ ′ ) and C ′ 1 := C ′ 1 ( d, d ∗ , β, j, V j ) , such that for any integers N 1 ≥ C , m 1 1 ≥ (( β ∨ 1) /d ∗ +1)log 2 N , 1 and p max 1 ≥ 6 d ∗ ( d + glyph[ceilingleft] γ 1 glyph[ceilingright] ) N , 1 there exists a network

$$\widetilde { \psi } _ { j } \in \mathcal { F } \left ( L _ { 1 }, ( d \sim p _ { 1 } ^ { \max } \sim d ^ { * } ), s _ { 1 } \right )$$

with depth L 1 = 9+( m 1 +5)(1+ log ( glyph[ceilingleft] 2 d ∨ γ 1 ) glyph[ceilingright] ) and number of parameters s 1 ≤ 142 d ∗ ( d + γ 1 +1) 3+ d N 1 ( m 1 +6) satisfying ,

$$\| \widetilde { \psi } _ { j } - \psi _ { j } \| _ { L ^ { \infty } ( V _ { j } ) } \leq C _ { 1 } ^ { \prime } N _ { 1 } ^ { - \frac { \beta \vee 1 } { d ^ { * } } } < \frac { \delta ^ { \prime } } { 4 }.$$

Given 0 &lt; η ≤ 1 2 / , set N 1 = glyph[ceilingleft] C 1 ∨ ( C ′ 1 ) d ∗ β ∨ 1 (4 r/η ) d ∗ β glyph[ceilingright] . Then, there exist positive constants K ,K ,K 1 ′ 1 ′′ 1 that do not depend on η, such that for any L 1 ≥ K 1 log(1 /η , ) any p max 1 ≥ K η ′ 1 -d /β ∗ and any s 1 ≥ K L η ′′ 1 1 -d /β ∗ ,

$$\inf _ { \widetilde { \psi } _ { j } \in \mathcal { F } ( L _ { 1 }, ( d \sim p _ { 1 } ^ { \max } \sim d ^ { * } ), s _ { 1 } ) } \| \widetilde { \psi } _ { j } - \psi _ { j } \| _ { L ^ { \infty } ( V _ { j } ) } \leq \left ( \frac { \eta } { 4 r } \right ) ^ { \frac { 1 } { \beta \wedge 1 } } \wedge \frac { \delta ^ { \prime } } { 4 }.$$

In the next step we construct a network approximating f ◦ ψ -1 j . By Lemma 2 (using that ψ j ( V j ) is bounded), we have that f ◦ ψ -1 j ∈ C β d ∗ ( ψ j ( V j )) . Combined with Lemma 5, this also shows that there exists δ ′ &gt; 0 , such that f ◦ ψ -1 j ∈ C β d ∗ ( ψ j ( V -δ j ) δ ′ ) . Using Theorem 1, there exist constants C 2 := C 2 ( d , β, δ , ψ ∗ ′ j ( V -δ j ) , K ′ ) and C ′ 2 := C ′ 2 ( d , β, ψ ∗ j ( V -δ j ) δ ′ , K ′ ) , such that for any integers N 2 ≥ C , m 2 2 ≥ ( β/d ∗ +1)log 2 N , 2 and p max 2 ≥ 6( d ∗ + glyph[ceilingleft] β glyph[ceilingright] ) N , 2 there exists a network

$$\overline { f \circ \psi _ { j } ^ { - 1 } } \in \mathcal { F } \left ( L _ { 2 }, \left ( d ^ { * } \sim p _ { 2 } ^ { \max } \sim 1 \right ), s _ { 2 } \right )$$

with depth L 2 = 9 + ( m 2 +5)(1 + glyph[ceilingleft] log 2 ( d ∗ ∨ β ) glyph[ceilingright] ) and number of parameters s 2 ≤ 142( d ∗ + β +1) 3+ d ∗ N 2 ( m 2 +6) such that ,

$$\| \overline { f \circ \psi _ { j } ^ { - 1 } } - f \circ \psi _ { j } ^ { - 1 } \| _ { L ^ { \infty } ( \psi _ { j } ( V _ { j } ^ { - \delta } ) ^ { \delta ^ { \prime } } ) } \leq C _ { 2 } ^ { \prime } N _ { 2 } ^ { - \frac { \beta } { d ^ { * } } }.$$

From f ◦ ψ -1 j we construct now a deep ReLU network ˜ f ◦ ψ -1 j with two output units computing f ◦ ψ -1 j / (1 + C N ′ 2 -β d ∗ ) and -f ◦ ψ -1 j / (1 + C N ′ 2 -β d ∗ ) . This network is then in the class F ( L , 2 ( d ∗ ∼ p max 2 ∼ 2 ) , 2 s 2 ) . Since f maps to [ -1 1] , , the network output of ˜ f ◦ ψ -1 j is in [ -1 1] , 2 . Also the output will approximate ( f ◦ ψ -1 j , -f ◦ ψ -1 j ) up to an error 2 C N ′ 2 -β d ∗ .

We can argue as above to find network architectures that lead to approximation error η/ r. 4 Set N 2 = glyph[ceilingleft] C 2 ∨ (8 rC /η ′ 2 ) d ∗ β glyph[ceilingright] . Then, there exist positive constants K ,K ,K 2 ′ 2 ′′ 2 that

do not depend on η, such that for any L 2 ≥ K 2 log(1 /η , ) any p max 2 ≥ K η ′ 2 -d /β ∗ and any s 2 ≥ K L η ′′ 2 2 -d /β ∗ ,

$$\inf _ { \widetilde { f \circ \psi _ { j } ^ { - 1 } } \in \mathcal { F } ( L _ { 2 }, ( d ^ { * } \sim p _ { 2 } ^ { \max } \sim 2 ), 2 s _ { 2 } ) } \left \| \widetilde { f \circ \psi _ { j } ^ { - 1 } } - ( f \circ \psi _ { j } ^ { - 1 }, - f \circ \psi _ { j } ^ { - 1 } ) \right \| _ { L ^ { \infty } ( \psi _ { j } ( V _ { j } ^ { \delta / 2 } \cap \mathcal { M } ) ^ { \delta ^ { \prime } / 2 } ) } \leq \frac { \eta } { 4 r }. \ ( 5. 3 )$$

Now, we build a deep network approximating τ j ∈ C βd/d ∗ d ( M , K 2 ) on M . For that, we again apply Theorem 1. Write γ 3 := βd/d . ∗ This shows existence of positive constants C 3 := C 3 ( d, d ∗ , β, M ) and C ′ 3 := C ′ 3 ( d, d ∗ , β, M ) , such that for any integers N 3 ≥ C , m 3 3 ≥ ( β/d ∗ +1)log 2 N , 3 and p max 3 ≥ 6( d + glyph[ceilingleft] γ 3 glyph[ceilingright] ) N , 3 there is a network

$$\bar { \tau } _ { j } \in \mathcal { F } \left ( L _ { 3 }, ( d \sim p _ { 3 } ^ { \max } \sim 1 ), s _ { 3 } \right )$$

with depth L 3 = 9+( m 3 +5)(1+ log ( glyph[ceilingleft] 2 d ∨ γ 3 ) glyph[ceilingright] ) and number of parameters s 1 ≤ 142 d ∗ ( d + γ 3 +1) 3+ d N 3 ( m 3 +6) satisfying ,

$$\| \overline { \tau } _ { j } - \tau _ { j } \| _ { L ^ { \infty } ( \mathcal { M } ) } \leq C _ { 3 } ^ { \prime } N _ { 3 } ^ { - \frac { \beta } { d ^ { * } } } < 1.$$

By adding one layer and two non-zero network parameters, we can also compute the network function ˜ τ j = ( τ j -C N ′ 3 -β d ∗ 3 ) + . This means that ˜ τ j ∈ F ( L 3 +1 ( , d ∼ p max 3 ∼ 1) , s 3 +2 ) and

$$\| \widetilde { \tau } _ { j } - \tau _ { j } \| _ { L ^ { \infty } ( \mathcal { M } ) } \leq 2 C _ { 3 } ^ { \prime } N _ { 3 } ^ { - \frac { \beta } { d ^ { \prime } } }.$$

↦

Moreover, on M , we have the property that the output of ˜ τ j is in [0 , 1] and that the support of x → ˜ τ j ( x ) is contained in the support of τ . j

Set N 3 = glyph[ceilingleft] C 3 ∨ (8 rC /η ′ 3 ) d ∗ β glyph[ceilingright] . Then, there exist positive constants K ,K ,K 3 ′ 3 ′′ 3 that do not depend on η, such that for any L 3 ≥ K 3 log(1 /η , ) any p max 3 ≥ K η ′ 3 -d /β ∗ and any s 3 ≥ K L η ′′ 3 3 -d /β ∗ ,

$$\inf _ { \widetilde { \tau } _ { j } \in \mathcal { F } ( L _ { 3 } + 1, ( d \sim p _ { 3 } ^ { \max } \sim 1 ), s _ { 3 } + 2 ) } \, \| \widetilde { \tau } _ { j } - \tau _ { j } \| _ { L ^ { \infty } ( \mathcal { M } ) } \leq \frac { \eta } { 4 r }.$$

In a next step, we combine the individual networks constructed so far in order to approximate τ j ( f ◦ ψ -1 j ) ◦ ψ j for any j = 1 , . . . , r.

First, we use the composition property (2.5). Recall that ψ j ( V j ) ⊂ [1 , ∞ ) d ∗ . We obtain that for any L 12 ≥ ( K 1 + K 2 ) log(1 /η , ) any p max 12 ≥ ( K ′ 1 ∨ K η ′ 2 ) -d /β ∗ and any s 12 ≥ 2( K ′′ 1 ∨ K ′′ 2 ) L 12 η -d /β ∗ , there exists a network ˜ f ◦ ψ -1 j ◦ ˜ ψ j = ˜ f ◦ ψ -1 j ◦ σ ψ ( ˜ j ) ∈ F ( L 12 +1 ( , d ∼ p max 12 ∼ 2) , s 12 ) such that both (5.2) and (5.3) hold. Using Lemma 6 with ε = δ / ′ 2 together

with (5.2) and ‖ ˜ f ◦ ψ -1 j ‖ L ∞ ( ψ j ( V -δ j ) δ ′ ) ≤ 1 for the first inequality and (5.2) and (5.3) for the second inequality gives

$$& \cdot \quad \cdot \quad \cdot \\ & \left \| \widetilde { ( f \circ \psi _ { j } ^ { - 1 } ) } \circ \widetilde { \psi _ { j } } - ( f, - f ) \right \| _ { L ^ { \infty } ( V _ { j } ^ { - \delta } ) } \\ & \leq \left \| \widetilde { \psi _ { j } } - \psi _ { j } \right \| _ { L ^ { \infty } ( V _ { j } ) } + \left \| \widetilde { f \circ \psi _ { j } ^ { - 1 } } - ( f \circ \psi _ { j } ^ { - 1 }, - f \circ \psi _ { j } ^ { - 1 } ) \right \| _ { L ^ { \infty } ( ( V _ { j } ^ { - \delta } ) ^ { s ^ { \prime } } ) } \\ & \leq \frac { \eta } { 2 r }.$$

In a next step, we synchronize the depth using (2.6). Thus, there exists a deep ReLU network E j with three outputs computing ( ˜ f ◦ ψ -1 j ◦ ˜ ψ , j -˜ f ◦ ψ -1 j ◦ ˜ ψ , τ j ˜ j ) and

$$E _ { j } \in \mathcal { F } \left ( 1 + L _ { 1 2 } \vee L _ { 3 }, ( d \sim p _ { 1 2 3 } ^ { \max } \sim 3 ), s _ { 1 2 } + s _ { 3 } + 2 + d ( L _ { 1 2 } \vee L _ { 3 } ) \right ),$$

with p max 123 := p max 3 + p max 12 .

For any positive integer m, there exists by Lemma 4 a network Mult m ∈ F ( m + 4 (2 , ∼ 6 ∼ 1)) , such that Mult m ( x, y ) ∈ [0 , 1] , | Mult m ( x, y ) -xy ∣ ∣ ≤ 2 -m , for all x, y ∈ [0 , 1] , and Mult m (0 , y ) = Mult( x, 0) = 0 . We can therefore also construct a neural network Mult ∗ ∈ F glyph[ceilingleft] ( log 2 ( r/η ) glyph[ceilingright] +6 (3 , ∼ 12 ∼ 2)) , that takes input ( x, y, z ) and outputs (Mult m ∗ ( x, z ) , Mult m ∗ ( y, z )) with m ∗ = log ( glyph[ceilingleft] 2 r/η ) glyph[ceilingright] +2 In particular, .

$$\left | \text{Multi} _ { m ^ { * } } \left ( x, z \right ) - \text{Multi} _ { m ^ { * } } \left ( \left ( - x \right ) _ { + }, z \right ) - x z \right | \leq \frac { \eta } { 4 r }$$

and Mult ( ∗ x, y, 0) = (0 0) , .

The composed network M j := Mult ∗ ◦ σ E ( j ) therefore computes approximately ( τ j · (( f ◦ ψ -1 j ) ◦ ψ j ) + , τ j · ( -( f ◦ ψ -1 j ) ◦ ψ j ) + = ( τ j · ( f ) + , τ j · ( -f ) + ) . Using the parallelization rule, we can now build r networks in parallel computing ( M ,... , M 1 r ) . The 2 r outputs of this network are by construction of Mult ∗ non-negative. Denote the two outputs of M j by M j 1 and M . j 2 By adding one layer computing a weighted sum of all the outputs, we have constructed the network

$$\widetilde { f } \coloneqq \sum _ { \ell = 1 } ^ { 2 } \sum _ { j = 1 } ^ { r } ( - 1 ) ^ { \ell + 1 } \sigma ( M _ { j \ell } ) = \sum _ { \ell = 1 } ^ { 2 } \sum _ { j = 1 } ^ { r } ( - 1 ) ^ { \ell + 1 } M _ { j \ell }.$$

Moreover, there exist positive constants c, C, C , ′ such that for any L ≥ c log(1 /η , ) any p ≥ Cη -d /β ∗ and any s ≥ C Lη ′ -d /β ∗ , ˜ f ∈ F ( L, ( d ∼ p ∼ 1) , s ) .

It remains to bound the approximation error of the network ˜ f. For the estimate, we use in the first step that due to Lemma 3 and the construction of ˜ τ j , for any j, τ j and ˜ τ j vanish outside the set V -δ j and Mult ( ∗ x, y, 0) = (0 0) , . The second inequality follows from (5.7).

For the third inequality, recall that ˜ τ j ≤ 1 and ‖ f ‖ L ∞ ( R d ) ≤ 1 . Together with (5.5) and (5.6), this yields

$$( 5. 6 ), \, \text{this yields} \\ \| \widetilde { f } - f \| _ { L ^ { \infty } ( \mathcal { M } ) } & \leq \sum _ { j = 1 } ^ { r } \left \| ( M _ { j 1 } - M _ { j 2 } ) - \tau _ { j } f \right \| _ { L ^ { \infty } ( V _ { j } ^ { - \delta } ) } \\ & \leq \frac { \eta } { 4 } + \sum _ { j = 1 } ^ { r } \left \| \widetilde { \tau } _ { j } ( \widetilde { f } \circ \psi _ { j } ^ { - 1 } ) \circ \widetilde { \psi } _ { j } - \tau _ { j } f \right \| _ { L ^ { \infty } ( V _ { j } ^ { - \delta } ) } \\ & \leq \frac { \eta } { 4 } + \sum _ { j = 1 } ^ { r } \left \| \widetilde { \tau } _ { j } - \tau _ { j } \right \| _ { L ^ { \infty } ( V _ { j } ) } + \left \| ( \widetilde { f } \circ \psi _ { j } ^ { - 1 } ) \circ \widetilde { \psi } _ { j } - f \right \| _ { L ^ { \infty } ( V _ { j } ^ { - \delta } ) } \\ & \leq \eta \\ \text{matinet} \, \text{the non-f} & \sqcap$$

completing the proof.

## References

- [1] Basri, R., and Jacobs, D. Efficient Representation of Low-Dimensional Manifolds using Deep Networks. arXiv e-prints (2016), arXiv:1602.04723.
- [2] Bauer, B., and Kohler, M. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. Ann. Statist. 47 , 4 (08 2019), 2261-2285.
- [3] Belkin, M., and Niyogi, P. Towards a theoretical foundation for Laplacian-based manifold methods. J. Comput. System Sci. 74 , 8 (2008), 1289-1308.
- [4] Bickel, P. J., and Li, B. Local polynomial regression on unknown manifolds , vol. 54 of Lecture Notes-Monograph Series . Institute of Mathematical Statistics, 2007, pp. 177-186.
- [5] Chui, C. K., and Mhaskar, H. N. Deep nets for local manifold learning. Frontiers in Applied Mathematics and Statistics 4 (2018), 12.
- [6] Eckle, K., and Schmidt-Hieber, J. A comparison of deep networks with relu activation function and linear spline-type methods. Neural Networks 110 (2019), 232 - 242.
- [7] Evans, L. C. Partial differential equations , second ed., vol. 19 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI, 2010.
- [8] Glorot, X., Bordes, A., and Bengio, Y. Deep sparse rectifier neural networks. In Aistats (2011), vol. 15, pp. 315-323.

| [9]   | Hamers, M., and Kohler, M. Nonasymptotic bounds on the L 2 -error of neural network regression estimates. Annals of the Institute of Statistical Mathematics 58 , 1 (2006), 131-151.                                                   |
|-------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [10]  | Hayakawa, S., and Suzuki, T. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. arXiv e-prints (2019), arXiv:1905.09195.                                                          |
| [11]  | Hein, M., Audibert, J.-Y., and von Luxburg, U. From graphs to manifolds- weak and strong pointwise consistency of graph Laplacians. In Learning theory vol. 3559 of Lecture Notes in Comput. Sci. Springer, Berlin, 2005, pp. 470-485. |
| [12]  | Horowitz, J. L., and Mammen, E. Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions. Ann. Statist. 35 , 6 (2007), 2589-2619.                                                    |
| [13]  | Imaizumi, M., and Fukumizu, K. Deep neural networks learn non-smooth functions effectively. PMLR 89 (2019), 869-878.                                                                                                                   |
| [14]  | Kohler, M., and Krzyzak, A. Adaptive regression estimation with multilayer feedforward neural networks. Journal of Nonparametric Statistics 17 , 8 (2005), 891- 913.                                                                   |
| [15]  | Kohler, M., and Krzy˙ak, z A. Nonparametric regression based on hierarchical interaction models. IEEE Trans. Inform. Theory 63 , 3 (2017), 1620-1630.                                                                                  |
| [16]  | Kohler, M., and Mehnert, J. Analysis of the rate of convergence of least squares neural network regression estimates in case of measurement errors. Neural Networks 24 , 3 (2011), 273 - 279.                                          |
| [17]  | Liang, S., and Srikant, R. Why deep neural networks for function approximation? ArXiv e-prints (Oct. 2016).                                                                                                                            |
| [18]  | Mhaskar, H. N. Neural networks for optimal approximation of smooth and analytic functions. Neural Computation 8 , 1 (1996), 164-177.                                                                                                   |
| [19]  | Mhaskar, H. N. Eignets for function approximation on manifolds. Appl. Comput. Harmon. Anal. 29 , 1 (2010), 63-87.                                                                                                                      |
| [20]  | Mhaskar, H. N., and Poggio, T. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications 14 , 06 (2016), 829-848.                                                                                      |
| [21]  | Nakada, R., and Imaizumi, M. Adaptive Approximation and Estimation of Deep Neural Network to Intrinsic Dimensionality. arXiv e-prints (2019), arXiv:1907.02177.                                                                        |

| [22]   | Petersen, P., Raslan, M., and Voigtlaender, F. Topological properties of the set of functions generated by neural networks of fixed size. arXiv e-prints (2018), arXiv:1806.08459.                                                    |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [23]   | Petersen, P., and Voigtlaender, F. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networks 108 (2018), 296 - 330.                                                                        |
| [24]   | Pinkus, A. Approximation theory of the MLP model in neural networks. Acta Numerica (1999), 143-195.                                                                                                                                   |
| [25]   | Poggio, T., Mhaskar, H., Rosasco, L., Miranda, B., and Liao, Q. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review. International Journal of Automation and Computing 14 , 5 (2017), 503-519. |
| [26]   | Schmidt-Hieber, J. Nonparametric regression using deep neural networks with ReLU activation function. To appear in Annals of Statistics (2017).                                                                                       |
| [27]   | Singer, A. From graph to manifold Laplacian: the convergence rate. Appl. Comput. Harmon. Anal. 21 , 1 (2006), 128-134.                                                                                                                |
| [28]   | Suzuki, T. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. arXiv e-prints (2018), arXiv:1810.08033.                                                    |
| [29]   | Telgarsky, M. Benefits of depth in neural networks. ArXiv e-prints (Feb. 2016).                                                                                                                                                       |
| [30]   | Tu, L. W. An introduction to manifolds , second ed. Universitext. Springer, New York, 2011.                                                                                                                                           |
| [31]   | Yarotsky, D. Optimal approximation of continuous functions by very deep ReLU networks. CoRR abs/1802.03620 (2018).                                                                                                                    |
Johannes Schmidt-Hieber
Deep ReLU network approximation of functions on a manifold
Whereas recovery of the manifold from data is a well-studied topic,
approximation rates for functions defined on manifolds are less known. In this
work, we study a regression problem with inputs on a $d^*$-dimensional manifold
that is embedded into a space with potentially much larger ambient dimension.
It is shown that sparsely connected deep ReLU networks can approximate a
H\"older function with smoothness index $\beta$ up to error $\epsilon$ using of
the order of $\epsilon^{-d^*/\beta}\log(1/\epsilon)$ many non-zero network
parameters. As an application, we derive statistical convergence rates for the
estimator minimizing the empirical risk over all possible choices of bounded
network parameters.