Title: THE UNIVERSAL APPROXIMATION POWER OF FINITE-WIDTH DEEP RELU NETWORKS

Abstract: We show that finite-width deep ReLU neural networks yield rate-distortion optimal approximation (Bölcskei et al., 2018) of a wide class of functions, including polynomials, windowed sinusoidal functions, one-dimensional oscillatory textures, and the Weierstrass function, a fractal function which is continuous but nowhere differentiable. Together with the recently established universal approximation result for affine function systems (Bölcskei et al., 2018) , this demonstrates that deep neural networks approximate vastly different signal structures generated by the affine group, the Weyl-Heisenberg group, or through warping, and even certain fractals, all with approximation error decaying exponentially in the number of neurons. We also prove that in the approximation of sufficiently smooth functions finite-width deep networks require strictly fewer neurons than finite-depth wide networks.

1. INTRODUCTION:

A theory establishing a link between the complexity of a neural network and the complexity of the function class to be approximated by the network was recently developed in Bölcskei et al. (2018) . Based on this framework, it was shown (Bölcskei et al., 2018 ) that all affine function classes are optimally representable by neural networks in the sense of Kolmogorov rate-distortion theory (Donoho, 1993; Grohs, 2015) . Equivalently, this means that the approximation error decays exponentially in the number of neurons employed in the approximation.

The present paper explores the question of whether the universality result established in Bölcskei et al. (2018) extends beyond affine function classes and answers it in the affirmative. Specifically, we consider the approximation of polynomials, windowed sinusoidal functions (Gröchenig & Samarah, 2000; Gröchenig, 2001) , one-dimensional oscillatory textures according to Demanet & Ying (2007) , and the Weierstrass function, a fractal function which is continuous everywhere and differentiable nowhere. The central conclusion of this paper is that finite-width ReLU networks of depth scaling poly-logarithmically in the inverse of the approximation error lead to exponentially decaying approximation error for all these different signal structures. This result is established by building on a recent breakthrough in Yarotsky (2016) and recognizing that the width of networks approximating polynomials need not scale linearly in the degree of the polynomial, but can actually be finite independently of the degree. This insight will also allow a sharp statement on the benefit of depth; specifically, we prove that in the approximation of sufficiently smooth functions finite-width deep networks require strictly fewer neurons than finite-depth wide networks.

Notation. For the function f (x) : R d → R, we define f L ∞ (Ω) := inf{C ≥ 0 : |f (x)| ≤ C, for all x ∈ Ω}. For a vector b ∈ R d , we let b ∞ := max i=1,...,d |b i |, similarly we write A ∞ := max i,j |A i,j | for the matrix A ∈ R m×n . We denote the identity matrix of size n × n by I n . Throughout, log stands for the logarithm to base 2.

2. SETUP AND BASIC RELU CALCULUS:

We start by defining ReLU neural networks.

Definition 2.1. Let L, N 0 , N 1 , . . . , N L ∈ N. A map Φ : R N0 → R N L given by

EQUATION

with affine linear maps W : R N -1 → R N , ∈ {1, 2, . . . , L}, and the ReLU activation function ρ(x) = max(x, 0), x ∈ R, acting component-wise (i.e., ρ(x 1 , . . . , x N ) := (ρ(x 1 ), . . . , ρ(x N ))) is called a ReLU neural network. The map W corresponding to layer is given by W (x) = A x+b , with A ∈ R N ×N -1 and b ∈ R N . We define the network connectivity as the total number of nonzero entries in the matrices A , ∈ {1, 2, . . . , L}, and the vectors b , ∈ {1, 2, . . . , L}. The depth of the network or, equivalently, the number of layers is L(Φ) := L and its width W(Φ) := max =0,...,L N . We further denote by B(Φ) := max =1,...,L max{ A ∞ , b ∞ } the maximum absolute value of the weights in the network.

We designate the class of ReLU networks Φ : R d → R N L with no more than L layers, width no more than M , input dimension d, and output dimension N L by N N L,M,d,N L . Note that the connectivity of Φ is upper-bounded by LM (M + 1).

For later use we record three technical results. We first record a technical lemma on the composition of neural networks.

1 Lemma 2.2. Let L 1 , L 2 , M 1 , M 2 , d 1 , d 2 , N L1 , N L2 ∈ N, Φ 1 ∈ N N L1,M1,d1,N L 1 , and Φ 2 ∈ N N L2,M2,d2,N L 2 with N L1 = d 2 .

Then, there exists a network

Ψ ∈ N N L1+L2,max{2N L 1 ,M1,M2},d1,N L 2 with B(Ψ) = max{B(Φ 1 ), B(Φ 2 )}, satisfying Ψ(x) = Φ 2 (Φ 1 (x)), for all x ∈ R d1 .

Before we can formalize the concept of a linear combination of neural networks, we need a result that shows how to augment network depth while retaining the networks input-output relation Lemma

2.3. Let L, M, K, d ∈ N, Φ 1 ∈ N N L,M,d,1

, and K > L. Then, there exists a corresponding network Φ 2 ∈ N N K,max{2,M },d,1 such that Φ 2 (x) = Φ 1 (x) for all x ∈ R d . Moreover, the weights of Φ 2 consist of the weights of Φ 1 and ±1's.

The next result formalizes the concept of a linear combination of neural networks.

Lemma 2.4. Let N, L i , M i , d i ∈ N, a i ∈ R, Φ i ∈ N N Li,Mi,di,1 , i = 1, 2, . . . , N , d = N i=1 d i . Then, there exist networks Φ 1 ∈ N N L,M,d,N and Φ 2 ∈ N N L,M,d,1 with L = max i L i , and M ≤ N i=1 max{2, M i } satisfying Φ 1 (x) = (Φ 1 (x 1 ) Φ 2 (x 2 ) . . . Φ N (x N )) T and Φ 2 (x) = N i=1 a i Φ i (x i ), for all x = (x T 1 , x T 2 , . . . , x T N ) T ∈ R d with x i ∈ R di , i = 1, 2, . . . , N .

Moreover, the weights of Φ 1 consist of the weights of the networks Φ i , i = 1, 2, . . . , N , and ±1's. The weights of Φ 2 consist of the weights of Φ 1 and {a 1 , a 2 , ..., a N }. Remark 2.5. Note that if the networks Φ i in Lemma 2.4 have shared inputs, the resulting networks Φ 1 and Φ 2 will have fewer than d = N i=1 d i inputs.

3. APPROXIMATION OF POLYNOMIALS:

This section shows how the multiplication operation and polynomials can be approximated to within error with ReLU networks of finite width and of depth poly-logarithmic in 1/ . We also note that the approximation results throughout the paper guarantee that the magnitude of the weights in the network does not grow faster than polynomially in the size of the domain over which approximation takes place. Although not shown here for space constraints, the combination of finite width, depth scaling poly-logarithmically in 1/ , and weights growing no faster than polynomially guarantees rate-distortion optimality in the sense of Bölcskei et al. (2018) and hence exponential error decay. Previous results on the approximation of the multiplication operation and of polynomials through finite-width ReLU networks reported in Hanin & Sellke (2017) ; Yarotsky (2018) do not come with bounds on the network weights, have depth scaling polynomially in 1/ , and therefore do not allow to conclude rate-distortion optimality.

The proof ideas for the results in this section are inspired by Yarotsky (2016) and by the "sawtooth" construction of Telgarsky (2015) . In contrast to Yarotsky (2016) , we consider networks without "skip connections" and of finite and explicitly specified width. Before starting with the approximation of x 2 , we note that all our results apply to the multivariate case as well, but we restrict ourselves to the univariate case for simplicity of exposition. Proposition 3.1. There exists a constant C > 0 such that for all ∈ (0, 1/2) there is a network Φ ∈ N N ∞,4,1,1 satisfying L(Φ ) ≤ C log( -1 ), B(Φ ) ≤ 4, Φ (0) = 0, and

EQUATION

With Proposition 3.1 we are now ready to show how ReLU networks can approximate the multiplication operation, which will then lead us to the approximation of arbitrary powers of x. Proposition 3.2. There exists a constant C > 0 such that for all D ∈ R + and ∈ (0, 1/2) there is a network

EQUATION

and Φ D, (0, x) = Φ D, (x, 0) = 0, for all x ∈ R.

The next result establishes that arbitrary polynomials can be approximated by ReLU networks of finite and explicitly specified width and of depth growing logarithmically in the inverse of the approximation error. In particular, the width of the approximating network does not grow with the degree of the polynomial as is the case in Yarotsky (2016), Ding et al. (2018) , Liang & Srikant (2017) . This finite-width aspect is central to the approximation of sinusoidal functions by ReLU networks as described in the next section. Proposition 3.3. There exists a constant C > 0 such that for all m ∈ N, A ∈ R + , p m (x) = m i=0 a i x i with max i=0,...,m |a i | = A, D ∈ R + , and ∈ (0, 1/2), there is a network Φ pm,D, ∈ N N ∞,16,1,1 satisfying L(Φ pm,D, ) ≤ Cm(log( A ) + log( -1 ) + m log( D ) + log(m)), B(Φ pm,D, ) ≤ max{A, 8 D 2m-2 }, and

EQUATION

Proof. We start by noting that for m = 1 the resulting affine function p 1 (x) = a 0 + a 1 x can be realized exactly, i.e., with = 0, by a network of depth L = 2 with

W 1 (x) = a 1 -a 1 x + a 0 -a 0 and A 2 = (1 -1), b 2 = 0.

The proof for m ≥ 2 will be effected by realizing the monomials x k , k ≥ 2, through iterative composition of multiplication networks and combining this with a construction which uses the network realizing x k not only as a building block in the network realizing x k+1 but also to construct the network approximating the partial sum k i=0 a i x i in parallel.

We start by setting

EQUATION

) can be realized through a neural network for all k ∈ N thanks to Lemma 2.2 and the fact that, as already noted above for the case m = 1, any affine function can be realized through a neural network.

We first show by induction that

EQUATION

for all η ∈ (0, 1/2), k ≥ 2. The base case k = 2 follows from

Ψ 2 D,η (x) -x 2 L ∞ ([-D,D]) = Φ H 1 D,η ,η (x, x) -x 2 L ∞ ([-D,D]) ≤ η.

We proceed to establishing the induction step (k -1) → k. The induction assumption is

Ψ k-1 D,η (x) -x k-1 L ∞ ([-D,D]) ≤ η k-3 s=0 D s . (6) Since Ψ k-1 D,η L ∞ ([-D,D]) ≤ x k-1 L ∞ ([-D,D]) + Ψ k-1 D,η (x) -x k-1 L ∞ ([-D,D]) ≤ H k-1 D,η , Propo- sition 3.2 implies that Ψ k D,η (x) -x k L ∞ ([-D,D]) ≤ Φ H k-1 D,η ,η (x, Ψ k-1 D,η (x)) -xΨ k-1 D,η (x) L ∞ ([-D,D]) + max [-D,D] |x| Ψ k-1 D,η (x) -x k-1 L ∞ ([-D,D]) ≤ η + D η k-3 s=0 D s = η k-2 s=0 D s ,

which completes the proof of the induction step.

We are now ready to proceed to the construction of the network Φ pm,D, approximating the polynomial p m (x) = m i=0 a i x i . To this end, we first note that the identity mapping x → x and the linear combination x, y → x + a i-1 y are affine transformations and can thus be realized by a network of depth L = 2. By Lemma 2.4 there hence exists a constant C 2 such that for every m ≥ 2,  and ∈ (0, 1/2 ). The network Φ pm,D, approximating the polynomial p m (x) = m i=0 a i x i is now constructed according to

p m (x) = m =0 a x , i ∈ {2, 3, . . . , m}, η ∈ (0, 1/2) there is a network ϕ i pm,D,η ∈ N N ∞,16,3,3 with L(ϕ i pm,D,η ) ≤ C 2 log( H i-1 D,η 2 η -1 ), and B(ϕ i pm,D,η ) ≤ max{4, 2 H i-1 D,η 2 , max i∈{0,...,m} |a i |} realizing the map (x s y) → x s + a i-1 y Φ H i-1 D,η ,η (x, y) .

The statements in the following apply for all:

m ∈ N, A ∈ R + , p m (x) = m i=0 a i x i with max i=0,...,m |a i | ≤ A, D ∈ R + ,

Φ pm,D, (x) := (0 1 a m ) ϕ m pm,D,η ϕ m-1 pm,D,η . . . ϕ 2 pm,D,η 1 0 1 x + 0 a 0 0 , with η := ( A m 2 D m ) -1 . This yields Φ pm,D, (x) = m i=0 a i Ψ i D,η (x), for all x ∈ R.

Hence equation 5 implies

Φ pm,D, (x) -p m L ∞ ([-D,D]) ≤ m i=0 |a i | Ψ i D,η (x) -x i L ∞ ([-D,D]) ≤ m i=2 |a i | η i-2 s=0 D s ≤ η max i∈{2,...,m} |a i | m i=2 (i -1) D i-2 ≤ Am 2 D m-2 η ≤ .

Thanks to its compositional structure, the width of Φ pm,D, equals the maximum width of the individual networks in the composition, i.e., W(Φ pm,D, ) ≤ 16.

Since H i-1 D,η ≤ 2 D m-1 , for i ≤ m, we further have L(Φ pm,D, ) ≤ m i=2 L(ϕ i pm,D,η ) ≤ m i=2 C 2 log( H i-1 D,η 2 η -1 ) ≤ C 2 m (log( A ) + log( -1 ) + (3m -2) log( D ) + 2 log(m) + 2) ≤ 4 C 2 m (log( A ) + log( -1 ) + m log( D ) + log(m)).

Finally, we note that

B(Φ pm,D, ) = max{1, |a 0 |, |a m |, max i∈{2,3,...,m} B(ϕ i pm,D,η )} ≤ max{A, 8 D 2m-2 }.

This finalizes the proof.

We conclude this section with a result on ReLU networks approximating smooth functions with exponential accuracy. The proof of this statement, provided in the supplement, is based on the theory developed above. Definition 3.4.

EQUATION

)

Lemma 3.5. There exist constants C > 0 and a polynomial π such that for all D ∈ R + , f ∈ S D , and

∈ (0, 1/2), there is a network Ψ f, ∈ N N ∞,23,1,1 satisfying L(Ψ f, ) ≤ C D (log( -1 )) 2 , B(Ψ f, ) ≤ max{1/D, D }π( -1

), and

EQUATION

)

Note that for expositional simplicity Lemma 3.5 covers functions defined on symmetric intervals [-D, D]. Close inspection of the proof reveals, however, that for arbitrary intervals [a, b] and functions

f ∈ C ∞ ([a, b], R) with f (n) L ∞ ([a,b]) ≤ n!, for all n ∈ N, the same statement (with D replaced by b -a in the bounds on L(Ψ f, ), B(Ψ f, )) holds.

4. APPROXIMATION OF SINUSOIDAL FUNCTIONS:

We are now ready to proceed to the approximation of sinusoidal functions. Theorem 4.1. There exists a constant C such that for every a,

D ∈ R + , ∈ (0, 1/2), there is a network Ψ a,D, ∈ N N ∞,16,1,1 satisfying L(Ψ a,D, ) ≤ C((log(1/ )) 2 + log( aD )), B(Ψ a,D, ) ≤ C, and Ψ a,D, -cos(a • ) L ∞ ([-D,D]) ≤ .

Proof. We start by approximating x → cos(2πx) on [0, 1]. To this end note the MacLaurin series representation

cos(x) = ∞ n=0 (-1) n (2n)! x 2n , ∀x ∈ R.

Thanks to the Taylor theorem with remainder in Lagrange form, we have, for all x ∈ [0, 1],

EQUATION

Next observe that n! ≥ ( n e ) n e, for all n ∈ N, which implies, (2π

) 4N +2 (2N + 1)! ≤ (4π 2 ) 2N +1 ( 2N +1 e ) 2N +1 e ≤ 4π 2 e 2N + 1 2N +1

, for all N ∈ N.

With N := 2π 2 e log(2/ ) , we get, for all ∈ (0, 1/2),

4π 2 e 2N + 1 2N +1 = 4π 2 e 2 2π 2 e log(2/ ) + 1 2 2π 2 e log(2/ ) +1 ≤ 2 -2π 2 e log(2/ ) ≤ 2 -log(2/ ) = 2 . (11) Noting that C 1 := max n∈N0 (2π) 2n (2n)! < ∞ and N ≤ C 2 log( -1

), for all ∈ (0, 1/2), with

C 2 := 4π 2 e + 1, application of Proposition 3.3 to p m (x) = p N (x) := N n=0 (-1) n (2n)! (2πx) 2n ,

with D = 1, establishes the following: There is a constant C 3 such that, for all ∈ (0, 1/2), there is a network Φ /2 satisfying

EQUATION

)

with W(Φ /2 ) ≤ 16, B(Φ /2 ) ≤ C 3 , and

L(Φ /2 ) ≤ C 3 N (log(C 1 ) + log(2/ ) + N log(1) + log(N )) ≤ C 4 (log( -1 )) 2 ,

where

C 4 := C 2 C 3 (1 + C 1 + C 2 ).

Combining equation 9, equation 10, equation 11, and equation 12, it follows that the network Φ /2 approximates the function x → cos(2πx) on [0, 1] to within accuracy , i.e., for all ∈ (0, 1/2), we have

EQUATION

)

We next extend this result to the approximation of x → cos(ax) on the interval [-1, 1] for arbitrary a ∈ R + . This will be accomplished by exploiting that x → cos(2πx) is 1-periodic and even. First recall the "sawtooth" functions g s : [0, 1] → [0, 1], s ∈ N, as defined in equation 24. It is straightforward, albeit somewhat tedious, to see that, for all

s ∈ N 0 , x ∈ [0, 1], cos(2π2 s x) = cos(2πg s (x)).

Similarly, it follows that cos(2π2 s x) = cos(2πg s (|x|)), for all s ∈ N 0 , x ∈ [-1, 1]. Next, note that for every a ∈ R + , there exists a C a ∈ (1/2, 1] such that a/(2π) = C a 2 log(a)-log(2π) ; we thus have, for all This concludes the proof.

EQUATION

An approximation result for sin(ax) can be obtained directly from Theorem 4.1 simply by noting that sin(x) = cos(x -π/2), which can be realized by the concatenation of a neural network that performs an affine transformation and a network that approximates cos(x). The formal statement is as follows.

Corollary 4.2. There exists a constant C > 0 such that for every a, 

EQUATION

EQUATION

The efficient approximation of functions in F D,a with a large is a notoriously difficult problem due to the combination of the rapidly oscillating cosine term and the warping g. The best available approximation results in the literature (Demanet & Ying, 2007) are based on wave-atom dictionaries2 and yield low-order polynomial approximation rates. In what follows we show that finite-width deep networks drastically improve these results to exponential approximation rates. Proposition 5.2. There exist a constant C > 0 and a polynomial π such that for all D, a ∈ R + , f ∈ F D,a , and ∈ (0, 1/2) there is a network Γ f, ∈ N N ∞,46,1,1 which satisfies

EQUATION

with L(Γ f, ) ≤ C( D (log( -1 )) 2 + log( aD )) and B(Γ f, ) ≤ max{1/D, π( -1 , D , a )}.

Finally, we show how the Weierstrass function-a fractal function, which is continuous everywhere but differentiable nowhere-can be approximated with exponential accuracy by deep ReLU networks. Specifically, we consider

EQUATION

Let α = -log(p) log(a) . It is well known (Zygmund, 2002) that W p,a possesses Hölder smoothness α which may be arbitrarily small, depending on p and a, see Figure 1 right. While classical approximation methods, for instance sparse approximation in frames, are not suitable owing to the warping operation, it turns out that deep finite-width networks achieve exponential approximation rate. The corresponding formal statement is as follows. Proposition 5.3. There exists a constant C > 0 such that, for all ∈ (0, 1/2), p

EQUATION

with L(Ψ p,a,D, ) ≤ C((log(1/ )) 3 + 2(log(1/ )) 2 log( a ) + log(1/ ) log(D)) and B(Ψ p,a,D, ) ≤ C.

6. FINITE DEPTH IS NOT ENOUGH:

We next show that, in the approximation of periodic functions, finite-width deep networks require asymptotically smaller connectivity than finite-depth wide networks. This statement is then extended to sufficiently smooth non-periodic functions, thereby formalizing the benefit of deep networks over shallow networks in the approximation of a broad class of functions.

We start with preparatory material taken from Telgarsky (2015) . Definition 6.1 (Telgarsky (2015) ). Let k ∈ N. A function f : R → R is called k-sawtooth if it is piecewise linear with no more than k pieces, i.e., its domain R can be partitioned into k intervals such that f is linear on each of these intervals. Lemma 6.2 (Telgarsky (2015) ).

Every Φ ∈ N N L,M,1,1 is (2M ) L -sawtooth. Definition 6.3. For a non-constant u-periodic function f ∈ C(R), we define ξ(f ) := inf δ∈[0,u), c,d∈R f (x) -(cx + d) L ∞ ([δ,u+δ]) .

The quantity ξ(f ) measures the error incurred by the best linear approximation of f on any segment of length equal to the period of f ; It can hence be interpreted as quantifying the non-linearity of f . The next result states that finite-depth networks with width scaling poly-logarithmically in the highest frequency of the periodic function to be approximated can not achieve arbitrarily small approximation error. Proposition 6.4. Let f ∈ C(R) be a non-constant u-periodic function, let L ∈ N and π a polynomial. Then there exists a ∈ R + such that for every network

Φ ∈ N N L,M,1,1 with M ≤ π(log(a)) it holds that f (ax) -Φ(x) L ∞ ([0,u]) ≥ ξ(f ) > 0.

Application of Proposition 6.4 shows that finite-depth networks, owing to ξ(cos) > 0, require faster than poly-logarithmic growth of connectivity in a to approximate x → cos(ax) with arbitrarily small error, whereas finite-width networks, thanks to Theorem 4.1, can accomplish this with polylogarithmic growth in connectivity. The next result, taken from (Frenzen et al., 2010) , allows us to extend this conclusion to non-periodic sufficiently smooth functions. Theorem 6.5 (Frenzen et al. (2010) ). Let Combining this with Lemma 6.2 yields the following statement on the depth-width tradeoff of networks approximating three-times continuously differentiable functions.

Theorem 6.6.

Let f ∈ C 3 ([a, b]) with b a

|f (x)|dx > 0, L ∈ N, and let π be a polynomial. Then there exists > 0 such that for every network

Φ ∈ N N L,M,1,1 with M ≤ π(log( -1 )) it holds that f -Φ L ∞ ([a,b]) ≥ .

This shows that any function which is at least three times continuously differentiable cannot be approximated by finite-depth networks of connectivity scaling poly-logarithmically. In contrast, as Proposition 3.3 and Theorem 4.1 show, finite-width networks can approximate various interesting types of smooth functions such as polynomials and sinusoidal functions at poly-logarithmic connectivity growth rates. Further results on the limitations of finite-depth networks akin to Theorem 6.6 were reported recently in Petersen & Voigtlaender (2017) .

and set g 0 (x) := x, g 1 (x) := g(x). We next briefly review a fundamental result from Yarotsky (2016) showing how the function f (x) := x 2 , x ∈ [0, 1], can be approximated by linear combinations of "sawtooth" functions g s . Specifically, let f m be the piecewise linear interpolation of f with 2 m + 1 uniformly spaced "knots" according to

f m k 2 m = k 2 m 2 , k = 0, . . . , 2 m , m ∈ N 0 .

The function f m approximates f with error m = 2 -2m-2 in the sense of

f m (x) -x 2 L ∞ [0,1] ≤ 2 -2m-2 .

Next, note that we can refine interpolation in the sense of going from f m-1 to f m by adjustment with a sawtooth function according to

EQUATION

)

This leads to the representation 

EQUATION

EQUATION

and since f m = ρ(f m ), ∀m ∈ N 0 , equation 25 can be rewritten as

EQUATION

Equivalently, equation 27 and equation 28 can be cast as a composition of affine linear maps and a ReLU nonlinearity according to

EQUATION

with

W 1 (x) = 2 -4 2 0 -2 -2m+1 2 -2m+2 -2 -2m+1 1    x 1 x 2 x 3 x 4    , W 2 (x) =    1 0 1 0 1 0 0 1    x 1 x 2 -    0 1/2 1 0    .

(30) Applying equation 29 iteratively initialized with g 0

EQUATION

and hence shows that f m can be realized through a network in N N m+1,4,1,1 with weights bounded (in magnitude) by 4. Since m = 2 -2m-2 and hence log(1/ m ) = 2m + 2, the statement follows upon noting that f m (0) = 0, ∀m ∈ N 0 .

A.5 PROOF OF PROPOSITION 3.2

Proof. The proof is based on the identity

EQUATION

which shows how multiplication can be implemented through the squaring operation. Let Ψ δ (x) be a neural network approximating x 2 according to Proposition 3.1, i.e.,

Ψ δ (x) -x 2 L ∞ [0,1] ≤ δ, Ψ δ (0) = 0.

We first extend this approximation result to the interval [-D, D], D > 1. Specifically, we need to find a ReLU network realization of x 2 and y 2 over [-D, D] and of (x + y) 2 over [-D, D] 2 . This will be accomplished by first noting that

EQUATION

and likewise

EQUATION

The network x → Ψ δ (|x|) has one layer more than the network x → Ψ δ (x) as it implements |x| = ρ(x) + ρ(-x) in its first layer. Next we define for every D ∈ R + , δ ∈ (0, 1/2) the network

EQUATION

and observe that Lemma 2.4 implies that there exists a constant C > 0 such that for all

D ∈ R + , δ ∈ (0, 1/2), x ∈ R it holds that L(Φ * D,δ ) ≤ C log(δ -1 ), W(Φ * D,δ ) = 12, B(Φ * D,δ ) ≤ max{4, 2 D 2 } and Φ * D,δ x, 0) = Φ * D,δ (0, x) = 0.

Using Equation 32 in combination with Equation 33 and Equation 34 yields

Φ * D,δ (x, y) - 1 2 (x + y) 2 -x 2 -y 2 L ∞ ([-D,D]) 2 ≤ 6 D 2 δ.

The proof is completed by taking for every

D ∈ R + , ∈ (0, 1/2) the network Φ D, := Φ * D,δ D, with δ D, := 6 D 2 .

A.6 PROOF OF LEMMA 3.5

Proof. We first consider the case D = 1. A fundamental result on Chebyshev interpolation, see e.g. (Liang & Srikant, 2017 , Lemma 3), guarantees, for all f ∈ S 1 , n ∈ N, the existence of a polynomial P f,n of degree n such that

EQUATION

Writing the polynomials P f,n as P f,n = n j=0 a f,n,j x j , crude-but sufficient for our purposesestimates show that there exists a constant c > 0 such that for all f ∈ S 1 , n ∈ N it holds that

EQUATION

and

EQUATION

)

In the following, we set n = log(2/ ) and Ψ f, = Φ P f,n ,1, /2 . Combining equation 36 and equation 38 establishes that for all f ∈ S 1 , ∈ (0, 1/2),

Ψ f, -f L ∞ ([-1,1]) ≤ Ψ f, -P f,n L ∞ ([-1,1]) + P f,n -f L ∞ ([-1,1]) ≤ 2 + 1 2 n ≤ 2 + 2 = .

Using log(2/ ) ≤ 2 log(2/ ) and log(2/ ) ≤ 2 log(1/ ), for all ∈ (0, 1/2), in equation 37 implies the existence of a constant C 2 such that for all f ∈ S 1 , ∈ (0, 1/2),

EQUATION

)

By the same token there exists a polynomial π 1 such that

B(Ψ f, ) = B(Φ P f,n ,1, /2 ) ≤ max{2 cn , 8} ≤ π 1 ( -1 ).

This completes the proof for the case D = 1.

We next prove the statement for D ∈ (0, 1). To this end, we start by noting that for g ∈ S D , with D ∈ (0, 1), the function

f g : [-1, 1] → R, x → g(Dx)

is in S 1 . Hence, there exists, for every

g ∈ S D , ∈ (0, 1/2), a network Ψ fg, ∈ N N ∞,16,1,1 satisfying sup x∈[-1,1] |Ψ fg, (x)-f g (x)| ≤ , L(Ψ fg, ) ≤ C 2 (log(1/ )) 2

, and B(Ψ fg, ) ≤ π 1 ( -1 ). The claim is established by taking the network approximating g(x) to be Ψ fg, (x) := Ψ fg, ( x D ) and noting that sup

x∈[-D,D] |Ψ fg, (x) -g(x)| = sup x∈[-D,D] |Ψ fg, ( x D ) -f g ( x D )| = sup x∈[-1,1] |Ψ fg, (x) -f g (x)| ≤ , L(Ψ fg, ) ≤ C 2 (log(1/ )) 2 , W(Ψ fg, ) ≤ 16, and B(Ψ fg, ) ≤ (1/D)π 1 ( -1 ).

It remains to prove the statement for the case D > 1. This will be accomplished by approximating f on intervals of length 2 (or less) and stitching the resulting approximations together using a localized partition of unity. To this end consider a, b ∈ R such that 1 ≤ b -a ≤ 2, and let

h ∈ C ∞ ([a, b], R) with h (n) L ∞ ([a,b]) ≤ n!, for all n ∈ N 0 . Next, note that the function x → h b-a 2 x + b+a 2 is in S 1 .

Hence, there exists, for every 

EQUATION

EQUATION

L(Ψ f,k, ) ≤ C 2 (log(4/ )) 2 , and B(Ψ f,k, ) ≤ max{2, 2|k|}π 1 ( -1 ). We next build a partition of unity through ReLU networks. Specifically, let χ

EQUATION

EQUATION

where Φ 2, /4 is the multiplication network from Proposition 3. 

f -f L ∞ ([-D,D]) ≤ ,

for all D > 1, f ∈ S D , ∈ (0, 1/2). It remains to be shown that the functions f can be realized by networks with the desired properties. To this end, consider for every

D > 1, f ∈ S D , k ∈ {1, . . . , 2N D + 1}, ∈ (0, 1/2), the network α f,k, ∈ N N ∞,19,1,1 given by α f,k, (x) := Φ 2, /4 (χ D,k-(N D +1) (x), Ψ f,k-(N D +1), (x)),

and the network β f,k, ∈ N N ∞,23,3,3 according to

β f,k, (x 1 , x 2 , x 3 ) := x 1 α f,k, (x 2 )

x 3

.

Further, set β 0 (x) := (x, 0, 0) T and let A ∈ R 3×3 be such that A(y 1 , y 2 , y 3 ) T = (y 1 , y 1 , y 2 + y 3 ) T , for all y 1 , y 2 , y 3 ∈ R. We can now define, for every

D > 1, f ∈ S D , ∈ (0, 1/2), the network Ψ f, ∈ N N ∞,23,1,1 given by Ψ f, (x) := (0 1 1) β f,2N D +1, (Aβ f,2N D , ( . . . (Aβ f,1, (Aβ 0 (x))))).

Direct calculation shows that f

(x) = Ψ f, (x), for all D > 1, f ∈ S D , ∈ (0, 1/2), x ∈ R.

Furthermore, thanks to Proposition 3.2, there exists a constant C 3 > 0 such that, for all D > 1,

EQUATION

EQUATION

This completes the proof. Applying Theorem 4.1 completes the proof.

A.8 PROOF OF PROPOSITION 5.2

Proof. For all D, a ∈ R + , f ∈ F D,a , let g f , h f ∈ S D be functions such that f = cos(ag f )h f holds. Note that Lemma 3.5 guarantees the existence of a constant C 1 > 0 and a polynomial π 1 such that for all D, a ∈ R + , f ∈ F D,a , ∈ (0, 1/2) there are networks This completes the proof.

Ψ h f , , Ψ g f , ∈ N N ∞,23,1,1 which satisfy L(Ψ h f , ), L(Ψ g f , ) ≤ C 1 D (log([ 12 a ] -1 )) 2 , B(Ψ h f , ), B(Ψ g f , ) ≤ max{1/D, D π 1 ([ 12 a ] -1 )} and Ψ g f , -g f L ∞ ([-D,D]) , Ψ h f , -h f L ∞ ([

A.9 PROOF OF PROPOSITION 5.3

Proof. For every N ∈ N, p ∈ (0, 1/2), a ∈ R + , x ∈ R, let S N,p,a (x) = N k=0 p k cos(a k πx). The geometric sum formula ensures that

EQUATION

)

Let N := log(2/ ) , ∈ (0, 1/2). Next note that Theorem 4.1 ensures the existence of a constant C 1 > 0 such that for all a, D ∈ R + , k ∈ N 0 , ∈ (0, 1/2) there is a network φ a k ,D, ∈ N N ∞,16,1,1 which satisfies L(φ a k ,D, ) ≤ C 1 ((log( -1 )) 2 + log( a k πD )), B(φ a k ,D, ) ≤ C 1 , and

EQUATION

)

Thanks to x = ρ(x) -ρ(-x) and Lemma 2.3, there exists, for every L ∈ N, a neural network τ L ∈ N N L,2,1,1 which satisfies for all x ∈ R that τ L (x) = x. For all p ∈ (0, 1/2), a, D ∈ R + , k ∈ N 0 , ∈ (0, 1/2), define the neural networks and let A ∈ R 3×3 be such that A(y 1 , y 2 , y 3 ) T = (y 1 , y 1 , y 2 + y 3 ) T , for all y ∈ R 3 . Consider now, for p ∈ (0, 1/2), a, D ∈ R + , ∈ (0, 1/2), the network Ψ p,a,D, defined by (52)

:

The proofs of the following two lemmata, along with all other proofs not provided in the paper, can be found in the supplement.

To be precise, the results inDemanet & Ying (2007) are concerned with the two-dimensional case, whereas we focus on the one-dimensional case. Note, however, that all our results can be readily extended to the multivariate case.

Figures and Tables:

Now recall that x → |x| = ρ(x) + ρ(-x) can be implemented by a 2-layer network and consider the realization of x → g log(a)-log(2π) (C a x), a ∈ R + , as developed in the proof of Proposition 3.1. Applying Lemma 2.2 twice, then establishes, thanks to (14), the existence of a constant C 5 such that the networkΨ a, := Φ /2 (g log(a)-log(2π) (C a |x|))approximates x → cos(ax) on [-1, 1] with accuracy , while satisfying L(Ψ a, ) ≤ C 5 ((log(1/ )) 2 + log( a )), W(Ψ a, ) ≤ 16, and B(Ψ a, ) ≤ C 5 .Finally, we consider the approximation of x → cos(ax) on intervals [-D, D], for arbitrary D ≥ 1.To this end, we define, for all a ∈ R + , D ∈ [1, ∞), ∈ (0, 1/2), the network Ψ a,D, (x) := Ψ aD, ( x D ) and observe that sup x∈[-D,D] |Ψ a,D, (x) -cos(ax)| = sup y∈[-1,1] |Ψ a,D, (Dy) -cos(aDy)| = sup y∈[-1,1]|Ψ aD, (y) -cos(aDy)| ≤ .

)with L(Ψ a,b,D, ) ≤ C((log( -1 )) 2 + log( aD + |b| )) and B(Ψ a,b,D, ) ≤ C.

Figure 1: Left: A function in F 1,100 . Right: The function W 1 √ 2 ,2 .

f ∈ C 3 ([a, b]) and consider a piecewise linear approximation of f on [a, b] that is accurate to within in the L ∞ ([a, b])-norm. The minimal number of linear pieces required to accomplish this scales according to s( ) ∼ c √ , → 0, where c =

(Ψ h, ) ≤ C 2 (log(1/ )) 2 , W(Ψ h, ) ≤ 16, and B(Ψ h, ) ≤ max{2, |b| + |a|}π 1 ( -1 ). Now, for D > 1, let N D ∈ N be such that 1 ≤ 2D N D ≤ 2 and consider the intervals I D,k := (k-1)D N D , (k+1)D N D , k ∈ {-N D , . . . , N D }. By equation 40 it follows that, for all D > 1, f ∈ S D , k ∈ {-N D , . . . , N D }, and ∈ (0, 1/2), there exists a network Ψ f,k, ∈ N N ∞,16,1,1 satisfying

2. Note that |f (x)| ≤ 1, for all x ∈ [-D, D], and |χ D,k (x)| ≤ 1, for all x ∈ [-D, D], k ∈ {-N D , . . . , N D }. Observe further that, for each x ∈ [-D, D], there are no more than 2 indices k such that χ D,k (x) = 0. Proposition 3.2 therefore implies that the sum in equation 43 has no more than 2 non-zero terms for each x ∈ [-D, D]. Combining equation 41, equation 42, and Proposition 3.2, and noting that supp(χ D,k ) = I D,k , hence yields

PROOF OF COROLLARY 4.2 Proof. For every a, D ∈ R + , b ∈ R, ∈ (0, 1/2) take the network given by Ψ a,b,D, (x) := Ψ a,D+ |b| a , (x -b a ) with Ψ a,D+ |b| a , according to Theorem 4.1 and observe that sup x∈[-D,D] |Ψ a,b,D, (x) -cos(ax -b)| = sup |b| a , (y) -cos(ay)| ≤ .

-D,D]) ≤ 12 a . (45)Theorem 4.1 further ensures the existence of a constant C 2 > 0 such that for all a, D ∈ R + , ∈ (0, 1/2) there is a neural networkΦ a,D, ∈ N N ∞,16,1,1 which satisfies L(Φ a,D, ) ≤ C 2 ((log(1/ )) 2 + log( aD )), B(Φ a,D, ) ≤ C 2 , and Φ a,D, -cos(a • ) L ∞ ([-D,D]) ≤ 3 .(46)Further, thanks to Proposition 3.2, there exists a constant C 3 > 0 such that for all ∈ (0, 1/2) there is a network µ ∈ N N ∞,12,2,1 which satisfies L(µ) ≤ C 3 log(1/ ), B(µ ) ≤ max{4, 2 D 2 },andsup x,y∈[-D,D] |µ (x, y) -xy| ≤ 3 .(47)For all D, a ∈ R + , f ∈ F D,a , ∈ (0, 1/2) we define the neural networksΓ f, := µ (Φ a,D, (Ψ g f , ), Ψ h f , ).(48)First, observe that Equation45, Equation46, andsup x∈R | d dx cos(ax)| = a imply for all x ∈ [-D, D] that |Φ a,D, (Ψ g f , (x)) -cos(ag f (x))| ≤ |Φ a,D, (Ψ g f , (x)) -cos(aΨ g f , (x))| + | cos(aΨ g f , (x)) -cos(ag f (x))| ≤ 3 + a 12 a ≤ 512 . Combining this with Equation45, Equation47, andcos L ∞ [-D,D] , f L ∞ [-D,D] ≤ 1 yields for all x ∈ [-D, D] that |Γ f, (x) -f (x)| = |µ (Φ a,D, (Ψ g f , (x)), Ψ h f , (x)) -cos(ag f (x))h f (x)| ≤ |µ (Φ a,D, (Ψ g f , (x)), Ψ h f , (x)) -Φ a,D, g f , (x))Ψ h f , (x)| + |Φ a,D, (Ψ g f , (x))Ψ h f , (x) -cos(ag f (x))h f (x)| ≤ 3 + 512 + 12 a + 5 12 12 a ≤ . By construction there exists a constant C 4 and a polynomial π 2 such that for all D, a ∈ R+ , f ∈ F D,a , ∈ (0, 1/2) it holds that W(Γ f, ) = 46, L(Γ f, ) ≤ L(µ ) + max{L(Φ a,D, ) + L(Ψ g f , ), L(Ψ h f , )} ≤C 4 D ((log( -1 )) 2 + log( a )), and B(Γ f, ) ≤ max{B(µ ), B(Φ a,D, ), B(Ψ g f , ), B(Ψ h f , )} ≤ max{1/D, π 2 ( -1 , D , a )}.

a 0 ,D, (x) 0 and ψ p,a,k D, (x 1 , x 2 , x 3 ) =   x 1 p k φ a k ,D, (x 2 )x 3 , k > 0, (51)

p,a,D, (x) := (0 1 1) ψ p,a,N D, (Aψ p,a,N -1 D, (. . . (Aψ p,a,0 D, (x)))).

While Yarotsky's constructionYarotsky (2016) is finalized by realizing equation 26 through a deep ReLU network of width 3 with the help of skip connectionsHe et al. (2016), i.e., connections between nodes in non-consecutive layers, we proceed by constructing an equivalent (in terms of input-output relation) network without skip connections and of width 4. As g

Table content: <table/>

Peer review (iclr2019):
 A main theme of the paper is showing that constant-width ReLU networks with depth increasing ploy-logarithmically in 1/.eps can achieve the desired accuracy over the classes considered. - It seems to me that a major claim of the paper is that previous results did not have constant-width approximations. However, this does not seem accurate to me. For example, for polynomials, the statement “the width of the approximating network does not grow with the degree of the polynomial as is the case in Yarotsky (2016)...” does not seem true. The constructions in Yarotsky (2016) which much of the present work appears to be based on, in fact, allow for a constant-width approximation of polynomials of degree “n” in “d”-variables, over the cube, with wdith = 9, and depth ~ m .log m [.log (1/.eps) + .log m] where m = n + d. (*) This bound is quite similar to Prop. 3.3 (with maybe even sharper dependence on “m”: m(.log m)^2 versus m^2 in the paper. PS. I would also double-check C in Prop. 3.3 which could be growing logarithmically in m.) (*) can be seen by inspecting the arguments around (14)-(15) in Yarotsky (2016) and noting that c_1 ~ .log m in that argument. For example, considering d=1 which is the focus of the present paper, Yarotsky (2016) shows a constant-width approximation to the product function (x,y) .mapsto xy which can be used to build a constant width-approximation to the monomial of the highest degree in the polynomial by recursive composition. All other monomials can be accessed serially at various depths of that architecture. - Much of the subsequent results in the paper are based on this constant-width approximation of polynomials as the authors point out. This is not that surprising given the Taylor approximation. For example, in Theorem 4.1, the first few lines of the proof show that the cosine can be approximated with a polynomial of degree m = O(.log (1/.eps)). Combining this with the polynomial approximation result one gets a constant-width approximation with depth ~ .log(1/.eps)^2 or .log(1.eps)^2 .log .log (1/.eps) depending which version of the polynomial approximation result one believes (m .log m versus m as the prefactor as discussed above). In other words, it appears to me that the proof of Theorem 4.1 can be shortened considerably. It would be a corollary of the polynomial approximation. - A novelty of the present work over Yarotsky (2016) that the authors point out is avoiding skip connections in Proposition 3.1. (Perhaps this is true also for Prop. 3.3? Not discussed.) I haven’t checked the details here, but assuming correctness, I agree that it is quite interesting. I am not sure however if it is a significant improvement over the existing results. - The discussion of Section 5 and 6 might be new in this context and somewhat interesting. However, at least that of Section 5 again seems to be a natural byproduct the polynomial approximation result. - I would like to point out that there are other results on finite-width approximation by ReLU networks, establishing some quite sharp bounds, for example, Hanin and Sellke 2017: arXiv:1710.11278 Yarotsky 2018: arXiv:1802.03620 In light of these, it wouldn’t be that accurate to claim that the issue of constant-width approximation is considered for the first time in the present paper.