Year: 2018

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.

text: We show that finite-width deep ReLU neural networks yield rate-distortion optimal approximation (Bö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 (Bö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.

heading: 1 INTRODUCTION
text: 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 Bölcskei et al. (2018). Based on this framework, it was shown (Bö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 Bö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 (Gröchenig & Samarah, 2000; Grö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) : Rd → R, we define ‖f‖L∞(Ω) := inf{C ≥ 0 : |f(x)| ≤ C, for all x ∈ Ω}. For a vector b ∈ Rd, we let ‖b‖∞ := maxi=1,...,d |bi|, similarly we write ‖A‖∞ := maxi,j |Ai,j | for the matrix A ∈ Rm×n. We denote the identity matrix of size n × n by In. Throughout, log stands for the logarithm to base 2.

heading: 2 SETUP AND BASIC RELU CALCULUS
text: We start by defining ReLU neural networks.
Definition 2.1. Let L,N0, N1, . . . , NL ∈ N. A map Φ : RN0 → RNL given by
Φ(x) =
{ W2(ρ (W1(x))), L = 2
WL(ρ (WL−1(ρ (. . . ρ (W1(x)))))), L ≥ 3 , (1)
with affine linear maps W` : RN`−1 → RN` , ` ∈ {1, 2, . . . , L}, and the ReLU activation function ρ(x) = max(x, 0), x ∈ R, acting component-wise (i.e., ρ(x1, . . . , xN ) := (ρ(x1), . . . , ρ(xN ))) is called a ReLU neural network. The mapW` corresponding to layer ` is given byW`(x) = A`x+b`, with A` ∈ RN`×N`−1 and b` ∈ RN` . 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,...,LN`. 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 Φ : Rd → RNL with no more than L layers, width no more than M , input dimension d, and output dimension NL by NNL,M,d,NL . 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 L1, L2,M1,M2, d1, d2, NL1 , NL2 ∈ N, Φ1 ∈ NNL1,M1,d1,NL1 , and Φ2 ∈ NNL2,M2,d2,NL2 with NL1 = d2. Then, there exists a network Ψ ∈ NNL1+L2,max{2NL1 ,M1,M2},d1,NL2 with B(Ψ) = max{B(Φ1),B(Φ2)}, satisfying Ψ(x) = Φ2(Φ1(x)), for all x ∈ Rd1 .
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 ∈ NNL,M,d,1, and K > L. Then, there exists a corresponding network Φ2 ∈ NNK,max{2,M},d,1 such that Φ2(x) = Φ1(x) for all x ∈ Rd. 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,Li,Mi, di ∈ N, ai ∈ R, Φi ∈ NNLi,Mi,di,1, i = 1, 2, . . . , N , d = ∑N i=1 di. Then, there exist networks Φ1 ∈ NNL,M,d,N and Φ2 ∈ NNL,M,d,1 with L = maxi Li, and M ≤ ∑N i=1 max{2,Mi} satisfying
Φ1(x) = (Φ1(x1) Φ2(x2) . . . ΦN (xN )) T and
Φ2(x) = N∑ i=1 aiΦi(xi),
for all x = (xT1 , x T 2 , . . . , x T N ) T ∈ Rd with xi ∈ Rdi , 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 {a1, a2, ..., aN}. 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 di inputs.

heading: 3 APPROXIMATION OF POLYNOMIALS
text: 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
1The proofs of the following two lemmata, along with all other proofs not provided in the paper, can be found in the supplement.
scaling poly-logarithmically in 1/ , and weights growing no faster than polynomially guarantees rate-distortion optimality in the sense of Bö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 x2, 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 Φ ∈ NN∞,4,1,1 satisfying L(Φ ) ≤ C log( −1), B(Φ ) ≤ 4, Φ (0) = 0, and
‖Φ (x)− x2‖L∞([0,1]) ≤ . (2)
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 allD ∈ R+ and ∈ (0, 1/2) there is a network ΦD, ∈ NN∞,12,2,1 satisfying L(ΦD, ) ≤ C log(dDe2 −1), B(ΦD, ) ≤ max{4, 2dDe2},
‖ΦD, (x, y)− xy‖L∞([−D,D]2) ≤ , (3) 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+, pm(x) =∑m i=0 aix
i with maxi=0,...,m |ai| = A, D ∈ R+, and ∈ (0, 1/2), there is a network Φpm,D, ∈ NN∞,16,1,1 satisfying L(Φpm,D, ) ≤ Cm(log(dAe) + log( −1) + m log(dDe) + log(m)), B(Φpm,D, ) ≤ max{A, 8dDe2m−2}, and
‖Φpm,D, − pm‖L∞([−D,D]) ≤ . (4)
Proof. We start by noting that for m = 1 the resulting affine function p1(x) = a0 + a1x can be realized exactly, i.e., with = 0, by a network of depth L = 2 with
W1(x) = ( a1 −a1 ) x+ ( a0 −a0 ) andA2 = (1 −1), b2 = 0. The proof form ≥ 2 will be effected by realizing the monomials xk, k ≥ 2, through iterative composition of multiplication networks and combining this with a construction which uses the network realizing xk not only as a building block in the network realizing xk+1 but also to construct the network approximating the partial sum ∑k i=0 aix i in parallel.
We start by setting HkD,η := dDek + η ∑k−2 s=0dDes, k ∈ N, and let ΦHkD,η,η , D ∈ R+, k ∈ N, η ∈ (0, 1/2), be multiplication networks according to Proposition 3.2. For D ∈ R+, k ∈ N, η ∈ (0, 1/2), we then recursively define ΨkD,η according to Ψ0D,η(x) = 1, Ψ1D,η(x) = x, and ΨkD,η(x) = ΦHk−1D,η ,η
(x,Ψk−1D,η (x)), k ≥ 2. Note that ΨkD,η(x) 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
‖ΨkD,η(x)− xk‖L∞([−D,D]) ≤ η k−2∑ s=0 dDes, (5)
for all η ∈ (0, 1/2), k ≥ 2. The base case k = 2 follows from
‖Ψ2D,η(x)− x2‖L∞([−D,D]) = ‖ΦH1D,η,η(x, x)− x 2‖L∞([−D,D]) ≤ η.
We proceed to establishing the induction step (k − 1)→ k. The induction assumption is
‖Ψk−1D,η (x)− x k−1‖L∞([−D,D]) ≤ η k−3∑ s=0 dDes. (6)
Since ‖Ψk−1D,η ‖L∞([−D,D]) ≤ ‖xk−1‖L∞([−D,D]) +‖Ψ k−1 D,η (x)−xk−1‖L∞([−D,D]) ≤ H k−1 D,η , Proposition 3.2 implies that
‖ΨkD,η(x)− xk‖L∞([−D,D]) ≤ ‖ΦHk−1D,η ,η(x,Ψ k−1 D,η (x))− xΨ k−1 D,η (x)‖L∞([−D,D])
+ max [−D,D]
|x|‖Ψk−1D,η (x)− x k−1‖L∞([−D,D])
≤ η + dDeη k−3∑ s=0 dDes = η k−2∑ s=0 dDes,
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 pm(x) = ∑m i=0 aix
i. To this end, we first note that the identity mapping x 7→ x and the linear combination x, y 7→ x + ai−1y are affine transformations and can thus be realized by a network of depth L = 2. By Lemma 2.4 there hence exists a constant C2 such that for every m ≥ 2, pm(x) =∑m `=0 a`x
`, i ∈ {2, 3, . . . ,m}, η ∈ (0, 1/2) there is a network ϕipm,D,η ∈ NN∞,16,3,3 with L(ϕipm,D,η) ≤ C2 log(dH i−1 D,ηe2η−1), and B(ϕipm,D,η) ≤ max{4, 2dH i−1 D,ηe2,maxi∈{0,...,m} |ai|} realizing the map
(x s y)> → ( x s+ ai−1y ΦHi−1D,η ,η (x, y) )> .
The statements in the following apply for all m ∈ N, A ∈ R+, pm(x) = ∑m i=0 aix
i with maxi=0,...,m |ai| ≤ A, D ∈ R+, and ∈ (0, 1/2). The network Φpm,D, approximating the polynomial pm(x) = ∑m i=0 aix i is now constructed according to
Φpm,D, (x) := (0 1 am)ϕ m pm,D,η ( ϕm−1pm,D,η ( . . . ϕ2pm,D,η (( 1 0 1 ) x+ ( 0 a0 0 )))) ,
with η := (dAem2dDem)−1 . This yields
Φpm,D, (x) = m∑ i=0 aiΨ i D,η (x), for allx ∈ R.
Hence equation 5 implies∥∥∥Φpm,D, (x)− pm∥∥∥ L∞([−D,D]) ≤ m∑ i=0 |ai|‖ΨiD,η (x)− x i‖L∞([−D,D]) ≤ m∑ i=2 |ai| ( η i−2∑ s=0 dDes )
≤ η max i∈{2,...,m} |ai| m∑ i=2 (i− 1)dDei−2 ≤ Am2dDem−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 Hi−1D,η ≤ 2dDe
m−1, for i ≤ m, we further have
L(Φpm,D, ) ≤ m∑ i=2 L(ϕipm,D,η ) ≤ m∑ i=2 C2 log(dHi−1D,η e 2η−1 )
≤ C2m (log(dAe) + log( −1) + (3m− 2) log(dDe) + 2 log(m) + 2) ≤ 4C2m (log(dAe) + log( −1) +m log(dDe) + log(m)).
Finally, we note that
B(Φpm,D, ) = max{1, |a0|, |am|, max i∈{2,3,...,m} B(ϕipm,D,η )} ≤ max{A, 8dDe 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. For D ∈ R+, let the set SD ⊆ C∞([−D,D],R) be given by
SD = { f ∈ C∞([−D,D],R) : ‖f (n)(x)‖L∞([−D,D]) ≤ n!, for all n ∈ N0 } . (7)
Lemma 3.5. There exist constants C > 0 and a polynomial π such that for all D ∈ R+, f ∈ SD, and ∈ (0, 1/2), there is a network Ψf, ∈ NN∞,23,1,1 satisfying L(Ψf, ) ≤ CdDe(log( −1))2, B(Ψf, ) ≤ max{1/D, dDe}π( −1), and
‖Ψf, − f‖L∞([−D,D]) ≤ . (8)
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.

heading: 4 APPROXIMATION OF SINUSOIDAL FUNCTIONS
text: 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, ∈ NN∞,16,1,1 satisfying L(Ψa,D, ) ≤ C((log(1/ ))2 +log(daDe)), B(Ψa,D, ) ≤ C, and
‖Ψa,D, − cos(a · )‖L∞([−D,D]) ≤ .
Proof. We start by approximating x 7→ cos(2πx) on [0, 1]. To this end note the MacLaurin series representation
cos(x) = ∞∑ n=0 (−1)n (2n)! x2n, ∀x ∈ R.
Thanks to the Taylor theorem with remainder in Lagrange form, we have, for all x ∈ [0, 1],∣∣∣∣∣cos(2πx)− N∑ n=0 (−1)n (2n)! (2πx)2n ∣∣∣∣∣ ≤ ∣∣∣∣ (2πx)2N+1(2N + 1)! ∣∣∣∣ sup t∈[0,1] | cos(2N+1)(2πt)| ≤ (2π) 4N+2 (2N + 1)! . (9)
Next observe that n! ≥ (ne ) ne, for all n ∈ N, which implies,
(2π)4N+2
(2N + 1)! ≤ (4π
2)2N+1
( 2N+1e ) 2N+1e
≤ ( 4π2e
2N + 1
)2N+1 , for allN ∈ N. (10)
With N := d2π2e log(2/ )e, we get, for all ∈ (0, 1/2),( 4π2e 2N + 1 )2N +1 = ( 4π2e 2d2π2e log(2/ )e+ 1 )2d2π2e log(2/ )e+1 ≤ 2−d2π 2e log(2/ )e
≤ 2− log(2/ ) = 2 .
(11)
Noting that C1 := ⌈ maxn∈N0 ( (2π)2n
(2n)!
)⌉ < ∞ and N ≤ C2 log( −1), for all ∈ (0, 1/2), with
C2 := 4π 2e+ 1, application of Proposition 3.3 to
pm(x) = pN (x) := N ∑ n=0 (−1)n (2n)! (2πx)2n,
with D = 1, establishes the following: There is a constant C3 such that, for all ∈ (0, 1/2), there is a network Φ /2 satisfying ∥∥∥Φ /2 − pN ∥∥∥
L∞([−1,1]) ≤ 2 , (12)
withW(Φ /2) ≤ 16, B(Φ /2) ≤ C3, and
L(Φ /2) ≤ C3N (log(C1) + log(2/ ) +N log(1) + log(N )) ≤ C4(log( −1))2,
where C4 := C2C3(1 + C1 + C2). Combining equation 9, equation 10, equation 11, and equation 12, it follows that the network Φ /2 approximates the function x 7→ cos(2πx) on [0, 1] to within accuracy , i.e., for all ∈ (0, 1/2), we have
‖Φ /2 − cos(2π · )‖L∞([0,1]) ≤ . (13)
We next extend this result to the approximation of x 7→ cos(ax) on the interval [−1, 1] for arbitrary a ∈ R+. This will be accomplished by exploiting that x 7→ cos(2πx) is 1-periodic and even. First recall the “sawtooth” functions gs : [0, 1] → [0, 1], s ∈ N, as defined in equation 24. It is straightforward, albeit somewhat tedious, to see that, for all s ∈ N0, x ∈ [0, 1],
cos(2π2sx) = cos(2πgs(x)).
Similarly, it follows that cos(2π2sx) = cos(2πgs(|x|)), for all s ∈ N0, x ∈ [−1, 1]. Next, note that for every a ∈ R+, there exists a Ca ∈ (1/2, 1] such that a/(2π) = Ca2dlog(a)−log(2π)e; we thus have, for all a ∈ R+, x ∈ [−1, 1],
cos(ax) = cos(2π2dlog(a)−log(2π)eCax) = cos ( 2πgdlog(a)−log(2π)e(Ca|x|) ) .
Since gdlog(a)−log(2π)e(Ca|x|) ∈ [0, 1], for all a ∈ R+, x ∈ [−1, 1], it follows from equation 13 that∥∥∥Φ /2(gdlog(a)−log(2π)e(Ca|x|))− cos(2πgdlog(a)−log(2π)e(Ca|x|))∥∥∥ L∞([−1,1])
= ∥∥∥Φ /2(gdlog(a)−log(2π)e(Ca|x|))− cos(ax)∥∥∥
L∞([−1,1]) ≤ .
(14)
Now recall that x 7→ |x| = ρ(x)+ρ(−x) can be implemented by a 2-layer network and consider the realization of x 7→ gdlog(a)−log(2π)e(Cax), 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 C5 such that the network Ψa, := Φ /2(gdlog(a)−log(2π)e(Ca|x|)) approximates x 7→ cos(ax) on [−1, 1] with accuracy , while satisfying L(Ψa, ) ≤ C5((log(1/ ))
2 + log(dae)),W(Ψa, ) ≤ 16, and B(Ψa, ) ≤ C5. Finally, we consider the approximation of x 7→ 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)| ≤ .
This concludes the proof.
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,D ∈ R+, b ∈ R, ∈ (0, 1/2) there is a network Ψa,b,D, ∈ NN∞,16,1,1 satisfying
‖Ψa,b,D, − cos(a · − b)‖L∞([−D,D]) ≤ , (15)
with L(Ψa,b,D, ) ≤ C((log( −1))2 + log(daD + |b|e)) and B(Ψa,b,D, ) ≤ C.

heading: 5 OSCILLATORY TEXTURES AND THE WEIERSTRASS FUNCTION
text: Consider the following function class consisting of one-dimensional “oscillatory textures” according to Demanet & Ying (2007).
Definition 5.1. Let the sets FD,a, D, a ∈ R+, be given by
FD,a = {cos(ag)h : g, h ∈ SD} . (16)
The efficient approximation of functions in FD,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 allD, a ∈ R+, f ∈ FD,a, and ∈ (0, 1/2) there is a network Γf, ∈ NN∞,46,1,1 which satisfies
‖Γf, − f‖L∞([−D,D]) ≤ , (17)
with L(Γf, ) ≤ C(dDe(log( −1))2 + log(daDe)) and B(Γf, ) ≤ max{1/D, π( −1, dDe, dae)}.
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
Wp,a(x) = ∞∑ k=0 pk cos(akπx), for p ∈ (0, 1/2], a ∈ R+. (18)
Let α = − log(p)log(a) . It is well known (Zygmund, 2002) that Wp,a possesses Hö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 constantC > 0 such that, for all ∈ (0, 1/2), p ∈ (0, 1/2], a ∈ R+, D ≥ 1, there is a network Ψp,a,D, ∈ NN∞,20,1,1 satisfying
‖Ψp,a,D, −Wp,a‖L∞([−D,D]) ≤ , (19)
with L(Ψp,a,D, ) ≤ C((log(1/ ))3 +2(log(1/ ))2 log(dae)+log(1/ ) log(D)) and B(Ψp,a,D, ) ≤ C.
2To be precise, the results in Demanet & 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.

heading: 6 FINITE DEPTH IS NOT ENOUGH
text: 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 Φ ∈ NNL,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 Φ ∈ NNL,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 7→ 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 f ∈ C3([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 = 1
4 ∫ b a √ |f ′′(x)|dx.
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 ∈ C3([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 Φ ∈ NNL,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).

heading: A PROOFS

heading: A.1 PROOF OF LEMMA 2.2
text: Proof. The proof is based on the identity x = ρ(x) − ρ(−x). First, note that by Definition 2.1, we can write
Φ1(x) = W 1 L1( ρ ( . . . W 1 1 (x))) and Φ2(x) = W 2 L2( ρ ( . . . W 2 1 (x))).
Next, define the affine map given by W̃ (x) = W 21 (( INL1 −INL1 ) x ) , for x ∈ R2NL1 , and note
that thanks to
W 21 (Φ1(x)) = W̃
( ρ (( W 1L1 −W 1L1 ) ( ρ ( . . .W 11 (x))) )) ,
the map
Ψ(x) = W 2L2
( ρ ( . . .W 22 ( ρ ( W̃ ( ρ (( W 1L1 −W 1L1 ) ( ρ ( . . .W 11 (x))) )))))) satisfies Ψ(x) = Φ2(Φ1(x)), for all x ∈ Rd1 , with L(Ψ) = L1 + L2, M(Ψ) ≤ 2M1 + 2M2, W(Ψ1) ≤ max{2NL1 ,W(Φ1),W(Φ2)}, and B(Ψ) ≤ max{B(Φ1),B(Φ2)}.

heading: A.2 PROOF OF LEMMA 2.3
text: Proof. The proof is based on the identity x = ρ(x)− ρ(−x). First, note that by equation 1 we can write Φ1(x) = WL( ρ ( . . .W1(x))). For K = L+ 1, Φ2 is given by
Φ2(x) = (1 −1) ρ ((
WL −WL
) ( ρ ( . . .W1(x))) ) ∈ NNL+1,max{2,M},d,1. (20)
For K > L+ 1, consider the network
Φ′1(x) = ( ρ(Φ1(x)) ρ(−Φ1(x)) ) = ( 1 0 0 1 ) ρ (( WL −WL ) ( ρ ( . . .W1(x))) ) ∈ NNL+1,max{2,M},d,2,
(21) which satisfies W(Φ′1) = max{2,W(Φ1)}. Next, we note that for every network of the form Ψ(x) = I2 ρ ( . . . ), the network Ψ′(x) := I2 ρ (Ψ(x)), (22) satisfies Ψ′(x) = Ψ(x), for all x ∈ Rd, L(Ψ′) = L(Ψ) + 1, and W(Ψ′) = max{W(Ψ), 2}. Moreover, the weights of Ψ′ consist of the weights of Ψ and {1}. Noting that Φ′1 in (21) is of the form I2 ρ ( . . . ) and iteratively applying the operation in equation 22 K − L − 2 times to Φ′1, we obtain a network Φ′′1 ∈ NNK−1,max{2,M},d,2. The proof is concluded by noting that Φ2 = (1 − 1)ρ (Φ′′1) ∈ NNK,max{2,M},d,1 satisfies Φ2(x) = Φ1(x), for all x ∈ Rd.

heading: A.3 PROOF OF LEMMA 2.4
text: Proof. Apply Lemma 2.3 to the networks Φi to get corresponding networks Φ̃i of depth L and set Φ1(x) := ( Φ̃1(x1), Φ̃2(x2), . . . , Φ̃N (xN ) )> , Φ2(x) := (a1, a2, . . . , aN )Φ1(x).

heading: A.4 PROOF OF PROPOSITION 3.1
text: Proof. Consider the function g : [0, 1]→ [0, 1],
g(x) =
{ 2x, if x < 12 ,
2(1− x), if x ≥ 12 , (23)
along with the “sawtooth” functions given by its s-fold composition
gs := g ◦ g ◦ · · · ◦ g︸ ︷︷ ︸ s , s ≥ 2, (24)
and set g0(x) := x, g1(x) := g(x). We next briefly review a fundamental result from Yarotsky (2016) showing how the function f(x) := x2, x ∈ [0, 1], can be approximated by linear combinations of “sawtooth” functions gs. Specifically, let fm be the piecewise linear interpolation of f with 2m + 1 uniformly spaced “knots” according to
fm ( k 2m ) = ( k 2m )2 , k = 0, . . . , 2m, m ∈ N0.
The function fm approximates f with error m = 2−2m−2 in the sense of
‖fm(x)− x2‖L∞[0,1] ≤ 2−2m−2.
Next, note that we can refine interpolation in the sense of going from fm−1 to fm by adjustment with a sawtooth function according to
fm(x) = fm−1(x)− gm(x)
22m . (25)
This leads to the representation
fm(x) = x− m∑ s=1 gs(x) 22s . (26)
While Yarotsky’s construction Yarotsky (2016) is finalized by realizing equation 26 through a deep ReLU network of width 3 with the help of skip connections He 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(x) = 2ρ(x)− 4ρ(x− 1/2) + 2ρ(x− 1), it follows that
gm = 2ρ(gm−1)− 4ρ(gm−1 − 1/2) + 2ρ(gm−1 − 1), (27)
and since fm = ρ(fm),∀m ∈ N0, equation 25 can be rewritten as fm = ρ(fm−1)− 2−2m ( 2ρ(gm−1)− 4ρ(gm−1 − 1/2) + 2ρ(gm−1 − 1) ) . (28)
Equivalently, equation 27 and equation 28 can be cast as a composition of affine linear maps and a ReLU nonlinearity according to(
gm fm
) = W1 ( ρ ( W2 ( gm−1 fm−1 ))) , (29)
with
W1(x) =
( 2 −4 2 0
−2−2m+1 2−2m+2 −2−2m+1 1 )x1x2x3 x4  , W2(x) = 1 01 01 0 0 1 (x1x2 ) −  01/21 0  . (30)
Applying equation 29 iteratively initialized with g0(x) = x, f0(x) = x yields( gm fm ) = W1 ( ρ ( W2 ( W1 ( ρ ( . . . ρ ( W2 ( W1 ( ρ ( W2 ( x x )))))))))) , (31)
and hence shows that fm can be realized through a network in NNm+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 fm(0) = 0,∀m ∈ N0.

heading: A.5 PROOF OF PROPOSITION 3.2
text: Proof. The proof is based on the identity
xy = 1
2 ((x+ y)2 − x2 − y2), (32)
which shows how multiplication can be implemented through the squaring operation. Let Ψδ(x) be a neural network approximating x2 according to Proposition 3.1, i.e., ‖Ψδ(x) − x2‖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 x2 and y2 over [−D,D] and of (x + y)2 over [−D,D]2. This will be accomplished by first noting that∥∥∥∥∥4dDe2Ψδ( |x|2dDe)− x2 ∥∥∥∥∥ L∞([−D,D]) ≤ 4dDe2δ, (33) and likewise ∥∥∥∥∥4dDe2Ψδ( |x+ y|2dDe )− (x+ y)2 ∥∥∥∥∥ L∞([−D,D])2 ≤ 4dDe2δ. (34)
The network x 7→ Ψδ(|x|) has one layer more than the network x 7→ Ψδ(x) as it implements |x| = ρ(x) + ρ(−x) in its first layer. Next we define for every D ∈ R+, δ ∈ (0, 1/2) the network
Φ∗D,δ(x, y) := 2dDe2 ( Ψδ ( |x+ y| 2dDe ) −Ψδ ( |x| 2dDe ) −Ψδ ( |y| 2dDe )) , (35)
and observe that Lemma 2.4 implies that there exists a constant C > 0 such that for allD ∈ R+, δ ∈ (0, 1/2), x ∈ R it holds that L(Φ∗D,δ) ≤ C log(δ−1),W(Φ∗D,δ) = 12, B(Φ∗D,δ) ≤ max{4, 2dDe2} and Φ∗D,δx, 0) = Φ ∗ D,δ(0, x) = 0. Using Equation 32 in combination with Equation 33 and Equation 34 yields ∥∥∥∥∥Φ∗D,δ(x, y)− 12 ( (x+ y)2 − x2 − y2 )∥∥∥∥∥
L∞([−D,D])2 ≤ 6dDe2δ.
The proof is completed by taking for every D ∈ R+, ∈ (0, 1/2) the network ΦD, := Φ∗D,δD, with δD, := 6dDe2 .

heading: A.6 PROOF OF LEMMA 3.5
text: 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 ∈ S1, n ∈ N, the existence of a polynomial Pf,n of degree n such that
‖f − Pf,n‖L∞([−1,1]) ≤ 12n(n+1)!‖f (n+1)‖L∞([−1,1]) ≤ 12n . (36) Writing the polynomials Pf,n as Pf,n = ∑n j=0 af,n,jx
j , crude—but sufficient for our purposes— estimates show that there exists a constant c > 0 such that for all f ∈ S1, n ∈ N it holds that
Af,n := max j=0,...,n
|af,n,j | ≤ 2cn.
Application of Proposition 3.3 to Pf,n establishes the existence of a constant C1 > 0 such that for all f ∈ S1, n ∈ N, ∈ (0, 1/2), there is a network ΦPf,n,1, /2 ∈ NN∞,16,1,1 satisfying B(ΦPf,n,1, /2) ≤ max{Af,n, 8} ≤ max{2cn, 8},
L(ΦPf,n,1, /2) ≤ C1n(cn+ log(2/ ) + log(n)), (37)
and
‖ΦPf,n,1, /2 − Pf,n‖L∞([−1,1]) ≤ 2 . (38)
In the following, we set n = dlog(2/ )e and Ψf, = ΦPf,n ,1, /2. Combining equation 36 and equation 38 establishes that for all f ∈ S1, ∈ (0, 1/2),
‖Ψf, − f‖L∞([−1,1]) ≤ ‖Ψf, − Pf,n ‖L∞([−1,1]) + ‖Pf,n − f‖L∞([−1,1]) ≤ 2 + 1 2n ≤ 2 + 2 = .
Using dlog(2/ )e ≤ 2 log(2/ ) and log(2/ ) ≤ 2 log(1/ ), for all ∈ (0, 1/2), in equation 37 implies the existence of a constant C2 such that for all f ∈ S1, ∈ (0, 1/2),
L(Ψf, ) = L(ΦPf,n ,1, /2) ≤ C2(log( −1))2. (39)
By the same token there exists a polynomial π1 such that
B(Ψf, ) = B(ΦPf,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 ∈ SD, with D ∈ (0, 1), the function fg : [−1, 1]→ R, x 7→ g(Dx) is in S1. Hence, there exists, for every g ∈ SD, ∈ (0, 1/2), a network Ψfg, ∈ NN∞,16,1,1 satisfying supx∈[−1,1] |Ψfg, (x)−fg(x)| ≤ , L(Ψfg, ) ≤ C2(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, ( xD )− fg( x D )|
= sup x∈[−1,1] |Ψfg, (x)− fg(x)| ≤ ,
L(Ψ′fg, ) ≤ C2(log(1/ )) 2,W(Ψ′fg, ) ≤ 16, and B(Ψfg, ) ≤ (1/D)π1( −1).
It remains to prove the statement for the caseD > 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 ∈ N0. Next, note that the function x 7→ h ( b−a 2 x+ b+a 2
) is in S1. Hence, there exists, for every ∈ (0, 1/2), a network Ψ′h, ∈ NN∞,16,1,1 such that supx∈[−1,1] |Ψ′h, (x)−h ( b−a 2 x+ b+a 2 ) | ≤ , L(Ψ′h, ) ≤ C2(log(1/ ))2, and B(Ψ′h, ) ≤ π1( −1).
The networks Ψh, (x) := Ψ′h, ( 2 b−ax− b+a b−a ) then satisfy
sup x∈[a,b] |Ψh, (x)− h(x)| = sup y∈[−1,1]
|Ψ′h, (y)− h ( b−a 2 y + b+a 2 ) | ≤ , (40)
L(Ψh, ) ≤ C2(log(1/ ))2, W(Ψh, ) ≤ 16, and B(Ψh, ) ≤ max{2, |b| + |a|}π1( −1). Now, for D > 1, let ND ∈ N be such that 1 ≤ 2DND ≤ 2 and consider the intervals
ID,k := [
(k−1)D ND , (k+1)DND
] , k ∈ {−ND, . . . , ND}.
By equation 40 it follows that, for all D > 1, f ∈ SD, k ∈ {−ND, . . . , ND}, and ∈ (0, 1/2), there exists a network Ψf,k, ∈ NN∞,16,1,1 satisfying
sup x∈ID,k |Ψf,k, (x)− f(x)| ≤ 4 , (41)
L(Ψf,k, ) ≤ C2(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 χ(x) = ρ(x + 1) − 2ρ(x) + ρ(x − 1), set χD,k(x) = χ( ND D x− k), D > 1, k ∈ Z, and note that χD,k ∈ NN 2,3,1,1. This yields a partition of unity according to ∑ k∈Z χD,k(x) = 1, for allx ∈ R. (42)
For D > 1, f ∈ SD, ∈ (0, 1/2), let f : R→ R be given by
f (x) := ND∑ k=−ND Φ2, /4(χD,k(x),Ψf,k, (x)), (43)
where Φ2, /4 is the multiplication network from Proposition 3.2. Note that |f(x)| ≤ 1, for all x ∈ [−D,D], and |χD,k(x)| ≤ 1, for all x ∈ [−D,D], k ∈ {−ND, . . . , ND}. Observe further that, for each x ∈ [−D,D], there are no more than 2 indices k such that χD,k(x) 6= 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) = ID,k, hence yields
‖f − f‖L∞([−D,D]) ≤ ,
for all D > 1, f ∈ SD, ∈ (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 ∈ SD, k ∈ {1, . . . , 2ND + 1}, ∈ (0, 1/2), the network αf,k, ∈ NN∞,19,1,1 given by
αf,k, (x) := Φ2, /4(χD,k−(ND+1)(x),Ψf,k−(ND+1), (x)),
and the network βf,k, ∈ NN∞,23,3,3 according to
βf,k, (x1, x2, x3) :=
( x1
αf,k, (x2) x3
) .
Further, set β0(x) := (x, 0, 0)T and let A ∈ R3×3 be such that A(y1, y2, y3)T = (y1, y1, y2 + y3)T , for all y1, y2, y3 ∈ R. We can now define, for every D > 1, f ∈ SD, ∈ (0, 1/2), the network Ψf, ∈ NN∞,23,1,1 given by
Ψf, (x) := (0 1 1)βf,2ND+1, (Aβf,2ND, ( . . . (Aβf,1, (Aβ0(x))))).
Direct calculation shows that f (x) = Ψf, (x), for all D > 1, f ∈ SD, ∈ (0, 1/2), x ∈ R. Furthermore, thanks to Proposition 3.2, there exists a constant C3 > 0 such that, for all D > 1, f ∈ SD, ∈ (0, 1/2),
W(Ψf, ) ≤ 4 + max k∈{1,...,2ND+1} W(αf,k, ) ≤ 23,
L(Ψf, ) = 2 + 2ND+1∑ k=1 L(βf,k, ) = 2 + 2ND+1∑ k=1 ( L(Φ2, /4) + max{L(χk−(ND+1)),L(Ψf,k−(ND+1), )} ) ≤ 2 + (2ND + 1)(C1 log(16 −1) + max{2, C2(log(4 −1))2}) ≤ C3D(log( −1))2,
and
B(Ψf, ) = max k∈{1,...,2ND+1} B(αf,k, ) ≤ max{8, 4D,max{2, 8D}π1( −1)} ≤ C ′dDeπ1( −1).
(44)
This completes the proof.

heading: A.7 PROOF OF COROLLARY 4.2
text: 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− ba ) 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 [−(D+ |b|a ),D+ |b| a ] |Ψ a,D+ |b| a , (y)− cos(ay)| ≤ .
Applying Theorem 4.1 completes the proof.

heading: A.8 PROOF OF PROPOSITION 5.2
text: Proof. For all D, a ∈ R+, f ∈ FD,a, let gf , hf ∈ SD be functions such that f = cos(agf )hf holds. Note that Lemma 3.5 guarantees the existence of a constant C1 > 0 and a polynomial π1 such that for all D, a ∈ R+, f ∈ FD,a, ∈ (0, 1/2) there are networks Ψhf , ,Ψgf , ∈ NN∞,23,1,1 which satisfy L(Ψhf , ),L(Ψgf , ) ≤ C1dDe(log([ 12dae ]
−1))2, B(Ψhf , ),B(Ψgf , ) ≤ max{1/D, dDeπ1([ 12dae ] −1)} and
‖Ψgf , − gf‖L∞([−D,D]), ‖Ψhf , − hf‖L∞([−D,D]) ≤ 12dae . (45)
Theorem 4.1 further ensures the existence of a constant C2 > 0 such that for all a,D ∈ R+, ∈ (0, 1/2) there is a neural network Φa,D, ∈ NN∞,16,1,1 which satisfies L(Φa,D, ) ≤ C2((log(1/ ))
2 + log(daDe)), B(Φa,D, ) ≤ C2, and ‖Φa,D, − cos(a · )‖L∞([−D,D]) ≤ 3 . (46)
Further, thanks to Proposition 3.2, there exists a constant C3 > 0 such that for all ∈ (0, 1/2) there is a network µ ∈ NN∞,12,2,1 which satisfies L(µ ) ≤ C3 log(1/ ), B(µ ) ≤ max{4, 2dDe2}, and
sup x,y∈[−D,D] |µ (x, y)− xy| ≤ 3 . (47)
For all D, a ∈ R+, f ∈ FD,a, ∈ (0, 1/2) we define the neural networks Γf, := µ (Φa,D, (Ψgf , ),Ψhf , ). (48)
First, observe that Equation 45, Equation 46, and supx∈R | ddx cos(ax)| = a imply for all x ∈ [−D,D] that
|Φa,D, (Ψgf , (x))− cos(agf (x))| ≤ |Φa,D, (Ψgf , (x))− cos(aΨgf , (x))| + | cos(aΨgf , (x))− cos(agf (x))|
≤ 3 + a 12dae ≤ 5 12 .
Combining this with Equation 45, Equation 47, and ‖ cos ‖L∞[−D,D], ‖f‖L∞[−D,D] ≤ 1 yields for all x ∈ [−D,D] that
|Γf, (x)− f(x)| = |µ (Φa,D, (Ψgf , (x)),Ψhf , (x))− cos(agf (x))hf (x)| ≤ |µ (Φa,D, (Ψgf , (x)),Ψhf , (x))− Φa,D, (Ψgf , (x))Ψhf , (x)|
+ |Φa,D, (Ψgf , (x))Ψhf , (x)− cos(agf (x))hf (x)| ≤ 3 + 5 12 + 12dae + 5 12 12dae ≤ .
By construction there exists a constant C4 and a polynomial π2 such that for all D, a ∈ R+, f ∈ FD,a, ∈ (0, 1/2) it holds thatW(Γf, ) = 46,
L(Γf, ) ≤ L(µ ) + max{L(Φa,D, ) + L(Ψgf , ),L(Ψhf , )} ≤ C4dDe((log( −1))2 + log(dae)), and
B(Γf, ) ≤ max{B(µ ),B(Φa,D, ),B(Ψgf , ),B(Ψhf , )} ≤ max{1/D, π2( −1, dDe, dae)}. This completes the proof.

heading: A.9 PROOF OF PROPOSITION 5.3
text: Proof. For every N ∈ N, p ∈ (0, 1/2), a ∈ R+, x ∈ R, let SN,p,a(x) = ∑N k=0 p
k cos(akπx). The geometric sum formula ensures that
|SN,p,a(x)−Wp,a(x)| ≤ ∞∑
k=N+1
|pk cos(akπx)| ≤ ∞∑
k=N+1
pk = 11−p − 1−pN+1 1−p ≤ 2 −N . (49)
Let N := dlog(2/ )e, ∈ (0, 1/2). Next note that Theorem 4.1 ensures the existence of a constant C1 > 0 such that for all a,D ∈ R+, k ∈ N0, ∈ (0, 1/2) there is a network φak,D, ∈ NN∞,16,1,1 which satisfies L(φak,D, ) ≤ C1((log( −1))2 + log(dakπDe)), B(φak,D, ) ≤ C1, and
‖φak,D, − cos(akπ · )‖L∞([−D,D]) ≤ 4 . (50)
Thanks to x = ρ(x) − ρ(−x) and Lemma 2.3, there exists, for every L ∈ N, a neural network τL ∈ NNL,2,1,1 which satisfies for all x ∈ R that τL(x) = x. For all p ∈ (0, 1/2), a,D ∈ R+, k ∈ N0, ∈ (0, 1/2), define the neural networks
ψp,a,0D, (x) =  xp0φa0,D, (x) 0  and ψp,a,kD, (x1, x2, x3) =  x1pkφak,D, (x2)
x3  , k > 0, (51) and let A ∈ R3×3 be such that A(y1, y2, y3)T = (y1, y1, y2 + y3)T , for all y ∈ R3. Consider now, for p ∈ (0, 1/2), a,D ∈ R+, ∈ (0, 1/2), the network Ψp,a,D, defined by
Ψp,a,D, (x) := (0 1 1)ψ p,a,N D, (Aψ p,a,N −1 D, (. . . (Aψ p,a,0 D, (x)))). (52)
Note Equation 50 combined with the geometric sum formula implies that for all p ∈ (0, 1/2), a,D ∈ R+, ∈ (0, 1/2), x ∈ [−D,D] we have
|Ψp,a,D, (x)− SN ,p,a(x)| = ∣∣∣∣∣ N ∑ k=0 pkφak,D, (x)− N ∑ k=0 pk cos(akπx) ∣∣∣∣∣ ≤
N ∑ k=0 pk|φak,D, (x)− cos(akπx)| ≤ 4 ∞∑ k=1 2−k = 2 .
Combining this with Equation 49 establishes that for all p ∈ (0, 1/2), a,D ∈ R+, ∈ (0, 1/2), x ∈ [−D,D] it holds
|Ψp,a,D, (x)−Wp,a(x)| ≤ 2−dlog( 2 )e + 2 ≤ 2 + 2 = .
By construction there exists a constant C2 such that for all p ∈ (0, 1/2), a,D ∈ R+, ∈ (0, 1/2) we haveW(Ψp,a,D, ) = 20,
L(Ψp,a,D, ) ≤ N ∑ k=0 L(φak,D, ) ≤ (N + 1)C1((log( −1))2 + log(daN πDe))
≤ C2((log( −1))3 + (log( −1))2 log(dae) + log( −1) log(D)),
and
B(Ψp,a,D, ) = max k∈{0,...,N } B(φak,D, ) = C1.
This completes the proof.

heading: A.10 PROOF OF PROPOSITION 6.4
text: Proof. First note that for every polynomial π̃ it holds that π̃(log(t)) ∈ O(t), t → ∞. Since x 7→ (2π(x))L is a polynomial, there exists a ∈ N such that a > (2π(log(a)))L. Lemma 6.2 now implies that any network Φ ∈ NNL,M,1,1 with M ≤ π(log(a)) is (2π(log(a)))L-sawtooth and therefore has less than a-many different linear pieces. Hence there exists an interval [u1, u2] ⊆ [0, u] with u2 − u1 ≥ (u/a) on which Φ is linear. Since u2 − u1 ≥ (u/a) the interval supports a full period of f(a · ) and we can therefore conclude that
‖f(a · )− Φ‖L∞([0,u]) ≥ ‖f(a·)− Φ‖L∞([u1,u2]) ≥ inf δ∈[0,u), c,d∈R ‖f(x)− (cx+ d)‖L∞([δ,u+δ]) = ξ(f).
Finally note, that ξ(f) > 0 holds by assumption, since any continuous u-periodic function which is linear on an interval of length u must be constant.

heading: A.11 PROOF OF THEOREM 6.6
text: Proof. The proof will be effected by contradiction. Assume that for every > 0 there exists a network Φ ∈ NNL,M,1,1 with M ≤ π(log( −1)) and ‖f − Φ ‖L∞([a,b]) ≤ . Since every ReLU network is piecewise linear we can now apply Theorem 6.5 to conclude that there exists a constant C such that for all > 0 the network Φ must have at least C − 1 2 many different linear pieces. This leads to a contradiction as, by assumption combined with Lemma 6.2, Φ is (2π(log( −1)))Lsawtooth and it holds for every polynomial π̃ that π̃(log( −1)) ∈ o( −1/2), → 0.

Review summaries:
The focus of this paper is to show that finite-width deep neural networks with fully connected layers and ReLU activations are rate-distortion optimal approximators of certain classes of functions, meaning the approximation error decays exponentially in the number of neurons in the network. The function classes explored in this paper are: 1-d polynomials (on bounded intervals), 1-d sinusoidal functions (on bounded intervals), and other 1-d functions built from compositions or linear combinations of these, such as the so-called class of “oscillatory textures” and a class of continuous but nowhere differentiable functions known as Weierstrass functions. Finally, the paper also shows that as the desired approximation accuracy goes to zero finite-width deep ReLU networks require asymptotically fewer neurons than finite-depth wide ReLU networks in approximating a broad class of smooth functions.