Minimum Width for Universal Approximation
Authors: Sejun Park
Chulhee Yun
Jaeho Lee
Jinwoo Shin
Venue: ICLR 2021 Spotlight (2021)
Keywords: universal approximation
neural networks

Abstract: The universal approximation property of width-bounded networks has been studied as a dual of classical universal approximation results on depth-bounded networks. However, the critical width enabling the universal approximation has not been exactly characterized in terms of the input dimension $d_x$ and the output dimension $d_y$. In this work, we provide the first definitive result in this direction for networks using the ReLU activation functions: The minimum width required for the universal approximation of the $L^p$ functions is exactly $\max\{d_x+1,d_y\}$. We also prove that the same conclusion does not hold for the uniform approximation with ReLU, but does hold with an additional threshold activation function. Our proof technique can be also used to derive a tighter upper bound on the minimum width required for the universal approximation using networks with general activation functions.

Published as a conference paper at ICLR 2021
MINIMUM WIDTH FOR UNIVERSAL APPROXIMATION
Sejun Park
Chulhee Yun
Jaeho Leel *KAIST EE
Jinwoo Shin
KAIST AI
MIT EECS
ABSTRACT
The universal approximation property of width-bounded networks has been studied dual of classical universal approximation results on depth- borih-bbunddd networks. However, the critical width enabling the universal approximation has not been exactly characterized in terms of the input dimension dz and the output dimension dy. In this work, we provide the first definitive result in this direction for networks using the RELU activation functions: The minimum width required for the univer- sal approximation of the L functions is exactly max(d, + 1, dy }. We also prove that the same conclusion does not hold for the uniform approximation with RELU, but does hold with an additional threshold activation function. Our proof technique can be also used derive a tighter upper bound on the minimum width required for the universal approximation using networks with general activation functions.
INTRODUCTION
The study of the expressive power of neural networks investigates what class of functions neural networks can/cannot represent approximate. Classical results in this field are mostly focused on shallow neural networks. An example of such results is the universal approximation theorem (Cybenko, 1989; Hornik al., 1989; Pinkus, 1999), which shows that neural network with fixed depth and arbitrary width can approximate any contimuous function on a compact set, up to arbitrary accuracy, if the activation function continuous and nonpolynomial. Another line of research studies the memory capacity of neural networks (Baum, 1988; Huang and Babri, 1998; Huang, 2003), trying to characterize the maximum number of data points that a given neural network can memorize.
After the advent of deep learning, researchers started to investigate the benefit of depth in the expressive power of neural networks, in an attempt understand the success of deep neural networks. This has led to interesting results showing the existence of functions that require the network to be extremely wide for shallow networks to approximate, while being easily approximated by deep and narrow networks (Telgarsky, 2016; Eldan and Shamir, 2016; Lin et al., 2017: Poggio et al., 2017). A similar trade-off between depth and width expressive power is also observed in the study of the memory capacity of neural networks (Yun et al., 2019; Vershynin, 2020).
In search of a deeper understanding the depth in neural networks, a dual scenario of the classical universal approximation theorem has also been studied (Lu et al., 2017; Hanin and Sellke, 2017; Johnson, 2019; Kidger and Lyons, 2020). Instead of bounded depth and arbitrary width studied in classical results, the dual problem studies whether universal approximation is possible with network of bounded width and arbilrary depth. A very interesting characteristic of this setting is that there exists a critical threshold on the width that allows a neural network to be a universal approximator. For example, one of the first results (Lu et al., 2017) in the literature shows that universal approximation possible for a width- + 4) REL.U network, but impossible for
of T,- functions from dd to width-d, RELU network. This implies that the minimum width required for universal approximation lies between d, + and d, + 4. Subsequent results have shown upper/lower bounds on the minimum width, but none of the results has succeeded in tight characterization of the minimum width.
1.1 WHAT IS KNOWN SO FAR?
Before summarizing existing results, we first define function classes studied in the literature. For domain X' C d and a codomain y Rdy, we define C(X,)) be the class of continuous
"maalls: sejun.park www.strkkaaita...... kr. chulheey mit.edu, jacho-Ice@ kc,,, jinwoos @ kai

---

Published as a conference paper at ICLR 2021
Table A summary of known upper/lower bounds on minimum width for universal approximation. In the table, K C Rd denotes a compact domain, and oo). "Conti." is short for continuous.
Reference
Function class
Activation p
Upper/lower bounds
L' R)
RELU
d₂ +1 S Wmin S dg +
Lu et al. (2017)
(KC, IR)
RELU
Wmin 2 dg
Hanin and Sellke (2017)
C(IC, Rd,)
RELU
d₂ + Wmin S dg + dy
Johnson (2019)
C(K,
uniformly conti.
Wmin 2 dg +
C(K, RRd))
conti. nonpoly+
Wmin S dz + dy + 1
Kidger and Lyons (2020)
C(K, R84)
nonaffine poly
Wmin _ d2 + dy + +2
IP(R", (P(R),
RELU
Wmin _ d2 dy
Ours (Theorem 1)
LP(K ))
RELU
Wmin = max (d, + 1, dzf
Ours (Theorem 2)
C[
RELU
Wmin = 3 > max d2 + 1, dg)
Ours (Theorem 3)
C(K, Rd))
RELU+STEP
Wmin = max + 1,
Ours (Theorem 4)
LP(K,
conti. nonpoly
Wmin I max(d, + 2, d +
1 requires that p is uniformly approximated by sequence of one-to-one functions.
1 requires that p is continuously differentiable some with p' (2) *0 0.
functions from X' to Vi endowed with the uniform norm: || =- supzex [+))) For p [1, o0), we also define L L2(X, y) to be the class of L functions from X' to V endowed with the To-norm: III1,, = (xx II lI) dx) The summary of known upper and lower bounds in the literature, as well as our own results, is presented in Table 1. We use Wmin to denote the minimum width for universal approximation.
First progress. As aforementioned, Lu et al. (2017) show that universal approximation of L (IR.,, IR) possible for width-(d, + 4) RELU network, but impossible for a width-d, RELU network. These results translate into bounds on the minimum width: de +1 1 S Wmin dg +4. Hanin and Sellke (2017) consider approximation of C(K, Rd),. where I. C Rd is compact. They prove that RELU networks of width d₂ dy dense in C(K, Rd), while width-d, RELU networks not. Although this result fully characterizes Wmin in case of dy = 1, it fails to do so for dy > 1.
General activations. Later, extensions to activation functions other than RELU have appeared in the literature. Johnson (2019) shows that if the activation function p is uniformly continuous and can be uniformly approximated by a sequence of one-to-one functions, a width-d, network cannot universally approximate C(K,R) Kidger and Lyons (2020) show that if p is continuous, nonpolynomial, and continuously differentiable at some with p' p((2) o O, then networks of width d, + dy + with activation p are dense in C(K,, Rdx). Furthermore, Kidger and Lyons (2020) prove that RELU networks of width d, + dy + 1 are dense in I [P(R (R"d., Rd)).
Limitations of prior arts. Note that none of the existing works succeeds in closing the gap between the upper bound (at least d + d,y) and the lower bound (at most d, + 1). This gap significant especially for applications with high-dimensional codomains (i.e., large dyy). arising for many practical applications of neural networks, e.g., image generation (Kingma and Welling, 2013; Goodfellow et al., 2014), language modeling (Devlin et al., 2019; Liu et al., 2019), and molecule generation (Gómez-Boome Bombarelli et al., 2018; Jin et al., 2018). In the prior arts, the main bottleneck for proving an upper bound below d, + d, is that they maintain all d, neurons to store the input and all d, neurons to construct the function output; this means every layer already requires at least d, + dy neurons. In addition, the proof techniques for the lower bounds only consider the input dimension d, regardless of the output dimension dy.
1.2 SUMMARY OF RESULTS
We mainly focus on characterizing the minimum width of RELU networks for universal approxi- mation. Nevertheless, our results are restricted RELU networks; they can be generalized to networks with general activation functions. Our contributions can be summarized as follows.
2

---

Published as a conference paper at ICLR 2021
Theorem states that the minimum width for RELU networks to be dense in LP(R (P is exactly max(d, + 1, d This is the first result fully characterizing the minimum width of RELÚ networks for universal approximation. In particular, the upper bound the minimum width is significantly smaller than the best known result d + dy + (Kidger and Lyons, 2020).
Given the full characterization of Wmin of RELU networks for approximating ( a natural question arises: Is Wmin also the same for C(K, TR We prove that it is not the case; Theorem 2 shows that the minimum width for RELU networks to be dense in C( 1], IR2) )) is 3. Namely, RELU networks of width max 1, 1 are not dense in C(K, Rd) in general.
In light of Theorem 2, is it impossible approximate C(C,, RR4) in general while maintaining width max(da (d. + 1, d Theorem 3 shows that an additional activation comes to rescue. We show that if networks use both RELU and threshold activation functions (which we refer as STEP)', they can universally approximate C(C, Bdv) with the minimum width max +,, dy).
Our proof techniques for tight upper bounds are restricted to RELU networks. In Theorem we extend our results to general activation functions covered in Kidger and Lyons (2020).
1.3
ORGANIZATION
We first define necessary notation in Section In Section 3, we formally state our main results and discuss their implications. In Section 4, we present "coding scheme" for proving upper bounds on the minimum width in Theorems 1, and 4. In Section 5, we prove the lower bound in Theorem by explicitly constructing counterexample. Finally, conclude the paper in Section 6. We note that all formal proof' of Theorems 1-4 are presented in Appendix.
2 PROBLEM SETUP AND NOTATION
Throughout this paper, we consider fully-connected neural networks that can be described as an alternating composition of affine transformations and activation functions. Formally, consider the following setup: Given a set of activation functions Σ, an I--layer neural network f of input dimension dz, output dimension dy. and hidden layer dimensions di,..., d 2 is represented
f= Ir or-1
l2 0 11,
where tę BRde1 Rede is an affine transformation and de vector of activation functions:
0e(#1, oe( Id,) (p1(zz), ................................ pa, (Ia,));
where & E. While mostly consider the cases where Σ is singleton (e.g., E (RELU)) also consider the case where Σ contains both RELU and STEP activation functions as in Theorem 3. We denote a neural network with Σ = {p} by "p network" and neural network with Σ {pi, by "P1+p2 network." We define the width w of f as the maximum over dj....,dy d1-1- We use "p networks (or P1 + P2 networks) of width w" for denoting the collection of all p networks (or P1 + P2 networks) of width w having a finite number of layers.
For describing the universal approximation of neural networks, we say P networks (or Pi+p2 networks) of width w are dense in C(X' ) if for any f E ((X,)) and æ > O, there exists a network (or a P1+P2 network) f of width w such that - f S E. Likewise, we say p networks (or Pi+P2 networks) are dense in [ (x',) (x))) ) if for any f" LP (X, )) and a > 0, there exists p network (or
Pr+p2 network) ʃ such that || - flpp S
MINIMUM WIDTH FOR UNIVERSAL APPROXIMATION
T.P approximation with RELU. We present our main theorems in this section. First, for universal approximation of (. Rd4) using RELU networks, we give the following theorem.
Theorem 1. For any E oo), RELU networks of width w are dense in LP ((dd=R,d) ) if and only if w max(d, + +, 1.
'The threshold activation function (i.c., STEP) denotes x. + 1[x 2 0). For simplicity of notation, let dg := d, and d, dy.
3

---

Published as a conference paper at ICLR 2021
This theorem shows that the minimum width Wnin for universal approximation is exactly equal to max dd. + 1, dy In order to provide a tight characterization of Wmin. we show three new upper and lower bounds: Wmin I max + 1, 1,dy) through a construction utillizing coding approach, Wmin 2 dy through a volumetric argument, and Wiinn 2 dr + 1 through an extension of the same lower bound for (Rd=, ,R4) (Lu et al., 2017). Combining these bounds gives the tight minimum width Wmin max d.z + 1,y
Notably, using our new proof technique, we overcome the limitation of existing upper bounds that require width at least dz + dl. Our construction first encodes the dz dimensional input vectors into one-dimensional codewords, and maps the codewords to target codewords using memorization, and decodes the target codewords to dy dimensional output vectors. Since we construct the map from input to target using scalar codewords, we bypass the need to use dæ + dy hidden nodes. More details are found in Section Proofs of the lower bounds are deferred to Appendix B.
Uniform approximation with RELU. In Theorem we have seen the tight characterization Wmin = max{d, dg + 1, d for , 1R)) functions. Does the same hold for C(C, R² for a compact IC C Rda2 Surprisingly, we show that the same conclusion does not hold in general. Indeed, we show the following result, proving that width max + 1,dy} is provably insufficient for dæ = 1, dg = 2.
Theorem 2. RELU networks of width w are dense in C[ 1J, IR? if and only if w 2 3.
Theorem 2 translates to wmin 3, and the upper bound Wniin S dr dy is given by Hanin and Sellke (0017). The key is to prove a lower bound Wmin 2 3, i.e., width 2 is not sufficient. Recall from Section 1.1 that all the known lower bounds are limited showing that width d,, is insufficient for universal approximation. A closer look at their proof techniques reveals that they heavily rely on the fact that the hidden layers have the same dimensions as the input space. As long as the width w de- their arguments break because such a network maps the input space into a gigens-dime space.
Although only for dg and dy 2. we overcome this limitation of the prior arts and show that width wo = 2 > du is insufficient for universal approximation, by providing a counterexample. We use novel topological argument which comes from a careful observation on the image created by RELU operations. In particular, we utilize the property of RELU U that it projects all negative inputs to zero, without modifying any positive inputs. We believe that our proof will be of interest to readers and inspire follow-up works. Please see Section 5 for more details.
Theorem and Theorem 2 together imply that for RELU networks, approximating C(K, IR,y) requires more width than approximating L (Rd, 1...). Interestingly, this is in stark contrast with existing results, where the minimum depth of RELU networks for approximating C(K, Rd) is two (Leshno al., 1993) but it is greater than two for approximating LP (RRd, Rdd)) (Wang and Qu, 2019).
Uniform approximation with RELU+STEP. While width max + 1, 1,dy is insufficient for RELU networks to be dense in C(K, IRd),, ), an additional STEP activation function helps achieve the minimum width max dz + 1, d as stated in the theorem below.
Theorem 3. RELU+STEP networks of width w are dense in C(KC, Rd4) if and only if 2 mmxx(ds + 1, ).
Theorem 2 and Theorem indicate that the minimum width for universal approximation is indeed dependent on the choice of activation functions. This is also in contrast to the classical results where RELU networks of depth 2 are universal approximators (Leshno et al., 1993), i.e., the minimum depths for universal approximation are identical for both RELU networks and RELU+STEP networks.
Theorem comes from a similar proof technique as Theorem 1. Due to its discontinuous nature, the STEP activation can be used in our encoder to quantize the input without introducing uniform norm errors. Lower bounds on Wmin can be proved a similar way as Theorem 1.
General activations. Our proof technique for upper bounds in Theorems and can be easily extended to networks using general activations. Indeed, we prove the following theorem, which shows that adding a width of 1 is enough to cover the networks with general activations.
Theorem 4. Let p R + R be any continuous nonpolynomial function which is continuously differentiable at some with p2(2) + 0. Then, networks of width w are dense in LP LP(,, Rd ( for all p E [1, 00) w 2 max(d, 2, dy + 11.
4

---

Published as a conference paper at ICLR 2021
I E [0.1]*
eacode (x)
encode f gk(#)
9M f" qu (w)
[0 10.100
(0.001,
0 0.100010.-- -01
0.001000 100
0.010
0.000,
encodex
memorizek,M
decode
0.011
0.100)
Figure 1: Illustration of the coding scheme
Please notice that unlike other theorems, Theorem 4 only proves an upper bound Wiin S max (dz dy 13. We note that Theorem 4 significantly improves over the previous upper bound of width dg + dy + by (Kidger and Lyons, 2020, Remark 4.1.).
4 TIGHT UPPER BOUND ON MINIMUM WIDTH
In this section, we present the main idea for constructing networks achieving the minimum width for universal approximation, and then sketch the proofs of upper bounds in Theorems 1, and 4.
4.1 CODING SCHEME FOR UNIVERSAL. APPROXIMATION
We now illustrate the main idea underlying the construction of neural networks that achieve the minimum width. To this end, we consider an approximation of a target continuous function f e C([O. 1] [0. 1]dx)): however, our main idea can be easily generalized to other domain, codomain, and LP functions. Our construction can be viewed as coding scheme in essence, consisting of three parts: encoder, memorizer, and decoder. First, the encoder encodes an input vector one-dimensional codeword. Then, the memorizer maps the codeword to a one-dimensional target codeword that is encoded with respect to the corresponding target f (xr). Finally, the decoder maps the target codeword to a target vector which is sufficienlly close to (x). Note that one can view the encoder, memorizer, and decoder functions mapping from dy-dimension 1-dimension, then to I-dimension, and finally to dyy-dimension
The spirit of the coding scheme is that the three functions can be constructed using the idea of the prior results such as (Hanin and Sellke, 2017). Recall that Hanin and Sellke (2017) approximate any continuous function mapping re-dimensional inputs m-dimmensional outputs using RELU networks of width n + m. Under this intuition, we construct the encoder, the memorizer, and the decoder by RELU+STEP networks (or RELU networks) of width d₂ + 1, 2, dy. respectively: these constructions result in the tight upper bound max(d, dN + 1, dy ). Here, the decoder requires width dy instead of dy + 1, as we only construct the first dy coordinates of the output, and recover the last output coordinate from a linear combination of the target codeword and the first dy coordinates. Note that we construct the exact encoder, decoder, and memorizer as prior results only approximate them.
Next, we describe the operation of each part. We explain their neural network constructions in subsequent subsections.
Encoder. Before introducing the encoder, first define quantization function g. |0, 1] C, for n E N and C, == 10,2 2
x 2 .,.,.. 2 2-n as
In (2) maxfc C. cs
In other words, given any x E [0, 1), 4n (x) preserves the first n bits in the binary representation of and discards the rest; = 1 is mapped always less than or equal to 2-
2-", Note that the error from the quantization is
The encoder encodes each input x E [0, 1]d= some scalar value via the function encodex IRd= Ca, k for some K E N defined as
encodex = Σ de UK (xx) x (i-1)K
In other words, encodex quantizes each coordinate of x by a K-bit binary representation and concatenates the quantized coordinates into single scalar value having a (d, K'bbit binary
5

---

Published as a conference paper at ICLR 2021
representation. Note that if one "decodes" codeword encode (2:) back to vector & as?
{ = (encode encodex C
then ||= a| < 2-K Namely, the "information loss" incurred by the encoding can be made arbitrarily small by choosing large K.
Memorizer. The memorizer maps each codeword encode (x) Cd, to its target codeword via the function memorizek,M, Ca, + Ca,as for some M E N, defined as
memorizek,M (encodex (+)) = encodem (f" (ạ(())
where yK is applied coordinate-wise for vector. We note that memorizem, is well-defined each encode (ar) Cd.K corresponds unique 9K (x) CK. Here, can observe that the target of the memorizer contains the information of the target value since encode (f* qk(x)) contains information of f at quantized version of æ, and the information loss due to quantization can be made arbitrarily small by choosing large enough K and M.
Decoder. The decoder decodes each codeword generated by the memorizer using the function decodem Cd, + ctty defined
decode := = where {2) encode (c) ch
Combining encode, memorize, and decode completes coding scheme for approximating f*. One can observe that our coding scheme is equivalent to gas f* o qK which can approximate the target function within any 0 error, i.e.,
suPaejo.11 IIf (x) decode o memorizek,M encode x (x) S
by choosing large enough K, M E N so that (y- 2 E.
In the remainder of this section, discuss how each part of the coding scheme can be implemented with neural network using RELU+STEP activations (Section 4.2), RELU activation (Section 4.3), and other general activations (Section 4.4).
4.2 TIGHT UPPER BOUND ON MINIMUM WIDTH OF RELU+STEP NETWORKS (THEOREM 3)
In this section, discuss how explicitly construct coding scheme to approximate functions in C(K,, Rdy) using a (idth-(max(d,, + 1, dly)) RELU+STEP network. This results the tight upper bound in Theorem 3.
First, the encoder consists of quantization functions чK and a linear transformation. However, as {K discontinuous and cannot be uniformly approximated by any continuous function, utilize the discontinuous STEP activation to exactly construct the encoder via a RELU+STEP network of width d, 1. On the other hand, the memorizer and the decoder maps finite number of scalar values (i.e., Ca, K and Cd, respectively) to their target values/vectors. Such maps can be easily implemented by piecewise linear functions; hence, they can be exactly constructed by RELU networks of width and dy, respectively, as discussed in Section 4.1. Note that STEP is used only for constructing the encoder.
In summary, all parts of our coding scheme can be exactly constructed by RELU+STEP networks of width d, + 1, and dy. Thus, the overall RELU+STEP network has width max(d, + dy). Furthermore, it can approximate the target continuous function f* within arbitrary uniform error by choosing sufficiently large K and M.
4.3 TIGHT UPPER BOUND ON MINIMUM WIDTH OF RELU NETWORKS (THEOREM 1)
The construction of width-(max + 1, d,,)) RELU network for approximating L (P ,dd))) (i.e., the tight upper bound in Theorem I) is almost identical to the RELU+STEP network construction
Here. encodex denotes the preimage of encodex and C& is the Cartesian product of d, copies of Cx. wyy- denotes the modulus of continuity of f [lf"(x)) (x) -f (x'))l wy (| x'1l oo)) Va, E 1]

---

Published as a conference paper at ICLR 2021
in Section 4.2. Since any L" function can be approximated by continuous function with compact support, we aim to approximate continuous f" [0, 1| - [0. 1]4, here as in our coding scheme.
Since the memorizer and the decoder can be exactly constructed by RELU networks, only discuss the encoder here. As we discussed in the last section, the encoder cannot be uniformly approximated by continuous functions (i.e., RELU networks). Nevertheless, it can be implemented by continuous functions except for a subset of the domain around the discontinuities, and this subset can be made arbitrarily small in terms of the Lebesgue measure. That is, we construct the encoder using a RELU network of width da + for [0. 1jdr except for a small subset, which enables us to approximate the encoder in the L norm. Combining with the memorizer and the decoder, we obtain RELU network of width [d + 1, dy } that approximates the target function f in the LP-norm.
4.4 TIGHTENING UPPER BOUND ON MINIMUM WIDTH OF GENERAL NETWORKS (THEOREM 4)
Our network construction can be generalized general activation functions using existing results on approximation of C(K, Rdv) functions. For example, Kidger and Lyons (2020) show that if the activation p is continuous, nonpolynomial, and continuously differentiable at some with d((z) # then p networks of width dz + dy + 1 are dense in C(K, TR Applying this result to our encoder, memorizer, and decoder constructions of RELU networks, it follows that if satisfies the conditions above, then networks of width max (d.- + +2, d, + 1} are dense in L"( R, i.e., Theorem 4 holds. We note that any universal approximation result for C(K, (&) by networks using other activation functions, other than Kidger and Lyons (2020), can also combined with our construction.
4.5 NUMBER OF LAYERS FOR MINIMUM WIDTH UNIVERSAL APPROXIMATORS
Lastly, we discuss the required number of layers for our network constructions achieving the tight minimum width in Theorem and First, our RELU + STEP network construction of width max + 1, 1,dy} for approximating /* E C((O, 1 Rdy) requires 0(24. K + 2 layers. Here, O(2*) layers are for the encoder, O(24.-K) layers are for the memorizer, and O(2M) layers for the decoder." Since K, .M must satisfy wy- (2-K))2))) )+2 M < for approximating f* s error (see Section 4.1), we choose K = [- (w (E/2)) M = [- log)(e/2)] so that (2 K) ). 2,2-M -M I E/2. Namely, the overall required number of layers (i.c., parameters) for approximating f in E error is (W (E/2)) (E/2)) -d + 1/s).
This number is closely related to the number of parameters for approximating arbitrary /* E C(O0, 1] RRdy) ) in & error: For RELU networks of constantly bounded number of layers, ((w77 (I))))) -dz) parameters are necessary and sufficient (Yarotsky, 2018). On the other hand, for RELU networks whose number of layers can increase with the number of parameters, (( (R(e)) dz./2) parameters sufficient (Yarotsky, 2018). However, while the number of lay- ers grows with the number of parameters in our construction, it requires ((=s)) + 1/e) parameters. Namely, the number of parameters in constructions achieving the tight minimum width can be improved.
Likewise, for proving the tight upper bound in Theorem 1, for approximating f E LP(R RR4) in e error, our RELU network construction also requires 3 (((())) + +1/8) layers where f is some continuous function satisfying I|f fllp = s/2.
TIGHT LOWER BOUND ON MINIMUM WIDTH
The purpose of this section is to prove the tight lower bound in Theorem 2, i.e., there exist f e C((O, R²) IR22
satisfying the following property: For any width-2 RELU network f. have IIf f fleo E. Our construction of f is based on topological properties of RELU networks, which we study in Section 5.1. Then, we introduce counterexample f" and prove that f cannot be approximated by width-2 RELU networks in Section 5.2.
and
"da. dy considered constants.
7

---

Published as a conference paper at ICLR 2021
5.1 TOPOLOGICAL PROPERTIES OF RELU NETWORKS
We first interpret a width-2 RELU network f R + IR² as below, following (I):
f = 000 ................................ 00..
where L E N denotes the number of layers. t IR + R2 and te R R2 for & > 1 are affine transformations, and the coordinate-wise RELU. Without loss of generality, we assume that tg is invertible for all >> 1, as invertible affine transformations are dense in the space of affine transformations on bounded support, endowed with the uniform norm. To illustrate the topological properties of better, we reformulate as follows:
( o a 1 o oo Φ2) ( o1)
where de and t are defined as t == tz o ....o .o and oz == (tz .... te+)) ii..,; ty Φ1 o tt. Under the reformulation (2), first maps inputs through affine
03-1
for f 2 2 and transformation 11, then it sequentially applies 0f o a o dh. Here, --- o o te can be viewed as changing the coordinate system using Φr, applying RELU in the modified coordinate system, and then returning back to the original coordinate system via 0r Under this reformulation, we present the following lemmas, whose proofs are presented in Appendices B.4-B.5.
Lemma 5. Let Φ IR2 - R²2 be invertible affine transformation. Then, there exist an, 02 R2 and b,, b2 E IR determined by & such that the following statements hold for S = {x (a), z) + 2 (a2, x) + b2 2 0} and x' Φ-1 (zz).
If E S, then x' = x.
e S, then X' + x and x' E OS.
Lemma 6. Let do TR. + RR2 be an invertible affine transformation. Suppose that x is in a bounded
path-component R2 T for some TT C R.. Then, the following statements hold for x' o 00 0 ((x) and T == 6- oo (TT).
If = x and x' & T', then x' is in bounded path-component R22 T.
Ifx' * x. then x' E TT'
Lemma 5 follows from the fact that output of RELU is identity to nonnegative coordinates, and is zero to negative coordinates. In particular, a1, by and 02 by in Lemma 5 correspond to the axes of the "modified" coordinate system before applying a. Under the same property of RELU, Lemma states that if a point æ is surrounded by set T. after applying ø o a o, either the point stays at the same position and surrounded by the image of or intersects with the image of T. Based on these observations, we are now ready to introduce our counterexample.
5.2 COUNTEREXAMPLE
Our counterexample f [0, 1] + R² is illustrated in Figure 2(a) where f ([0, pı]) is drawn in red from (4,3) to (0, 0). ((P1(p P2)) drawn in black from (0,0) 0) to (-1, and [[p(p,, 1)) is drawn in blue from (-1, to (1, 0), for some 0 < Pı < P2 < 1, e.g. P1 = 3: = 3 In this section, we suppose for contradiction that there exists RELU network ff of width 2 such that I|f - flloo S 100 To this end, consider the mapping by the first l layers of f:
1
ge == (07' oo 0e) o ... (6-l 0000)00))))
Our proof is based on the fact: ge ge(x'), then fxx = f'(x'.. Thus, the following must hold:
if il flloo S - then ge (0. PI)) ge ([p2, 1)) for all
(3)
Let B = (-2,2) x 1) (the gray box in Figure 2(b)) and &" N be the largest & such that of oo o (B) * B. This means that after the -t layer, everything inside the box B never gets
6 aS denotes the boundary set of S.
S C T is a path-component of T if S is maximal set satisfying the following condition: For any 31 22 E S, there exists continuous function f: [0, 1] + such that f(0) 2i and f(1) = Ø2.
8

---

Published as a conference paper at ICLR 2021
R
3
2-
-1
-2
-3
-4-
=1=
3-
21
5---3-32--2 0 15
= 5-----2----
(a)
(b)
(c)
Figure 2: (a) Illustration of the image of f": :00. + R (b, c) Examples of ge- (10, 1]).
affected by RELU operations. In other words, f(00, 1J) n must have been constructed in the first ex layers. Under this observation, the boundary of S in Lemma 5 determined by Φg- must intersect with B: If B C S, then $z- o (B( B which contradicts the definition of L and BnS then f([o. 11) n B cannot be constructed in the first L" layers. Therefore, there must exist a line (e.g.. a line containing one boundary of S, see the arrow in Figure 2(b)) intersecting with B, such that the image ge- ((0, 1]) lies in one side of the line. Since the image of the entire network f([0, pi)) is on both sides of the line, we have ge- (10, Pıl) # f(0. pıl). which implies that the remaining layers \ B to f(00, Pıl) \ B; this also implies ge phl) \ B of 0. A similar argument gives ge. (122, 1)) B + 0.
e + l..... L 1 must have moved the image ge- ([0, p1l)
Since f([0, 1]) n B must have been constructed in the first 6 layers, illustrated in Figures 2(b) and 2(c), the boundary ØB intersects with ge- ([p2. 11) (the blue line) near points (-1, 1) and (1, 1). Hence, T : gr- ([p2, 1I) U B forms "closed loop." Also, 0B intersects with gr- ([0. pıl) near the point (0, 1), so there must exist a point in ge- ([0, \ B that "surrounded" by T. Given these observations, we have the following lemma. The proof of Lemma 7 is presented in Appendix B.6.
Lemma 7. The image gr- (1)) 1) B is contained in a bounded path-componen Rf? T unless ge- (10, p.l) O ge- (lp2, 1]) 7 0.
Figures 2(b) and 2(c) illustrates the two possible cases of Lemma 7. If ge- (10, n ge ((22, 1)) *
(Figure 2(c)), this contradicts (3). Then, ge- ([0, p1 1) B must be contained in bounded path- component of I T. Recall that gr- {[0, p1)) \ B has to move to S[O0, pı]) B by layers l However, by Lemma if any point in ge- (00, pı)) \ moves, then it must intersect
1...., T. with the image of T. If it intersects with the image of ge- ((p2. 1]). then (3) is violated, hence a contradiction. If intersects with B at the -i layer for some el > 8", then B & S for in Lemma determined by é Hence, it violates the definition of L" Φ5 o dee (B) # B by Lemma 5. Namely, the approximation by is impossible any cases. This completes the proof of Theorem 2.
CONCLUSION
The universal approximation property of width-bounded networks is one of the fundamental problems in the expressive power theory deep learning. Prior arts attempt to characterize the minimum width sufficient for universal approximation; however, they only provide upper and lower bounds with large gaps. In this work, we provide the first exact characterization of the minimum width of RELU networks and RELU+STED networks. In addition, minimum width on the target function classes and activation functions, in contrast to the minimum depth of classical results. We believe that our results and analyses would contribute to a better understanding of the performance of modern deep and narrow network architectures.
observe interesting dependence of the
ACKNOWLEDGEMENTS
This work was supported by Institute of Information & Communications Technology Planning & Evaluation (ITTP) grant funded by the Korea government (MSIT) (N0.2019-0-00075. Artificial Intelligence Graduate School Program (KAIST) and No.2017-0-01779. A machine learning and statistical inference framework for explainable artificial intelligence). Chulhee Yun acknowledges financial supports from Korea Foundation for Advanced Studies, NSF CAREER grant 1846088, and ONR grant N00014-20-1-2394

---

Published as a conference paper at ICLR 2021
REFERENCES
Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 4(3):193-215, 1988. ISSN 0885-064X.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4)3303-314 1989.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on Learning Theory, 2016.
Rafael Gómmzz-Bombrdee Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobate Benjamín Sánchez- Lengellng, Dennis Sheberla, Jorge Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven continuous representation of molecules. ACS Central Science, 4(2):268- 276. 2018.
Timothy D Hirzel,
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, 2014.
Richard Hacker. Certification of algorithm 112: position of point relative to polygon. Commumications of the ACM, 5(12):606, 1962.
Boris Hanin and Mark Sellke. Approximating continuous functions by ReLU nets of minimal width. arXiv preprint 1710.11 2017.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989.
Guang- Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE Transactions on Neural Networks, 14(2):274-281, 2003.
Guang-Bin Huang and Haroon A Babri. Upper bounds the number of hidden neurons in feed- forward networks with arbitrary bounded nonlinear activation functions. IEEE Transactions on Neural Networks, 91):224-229, 1998.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. International Conference on Machine Learning, 2018.
Jesse Johnson. Deep, skinny neural networks not universal approximators. In International Conference on Learning Representations, 2019.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on Learning Theory, 2020.
Diederik Kingma and Max Welling, Auto-encoding variational bayes. In International Conference on Learning Representations, 2013.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993.
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work well? Journal of Statistical Physics, 168(6))223-1144 2017.
Yinhan Liu, Myle Ott. Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
10

---

Published as a conference paper at ICLR 2021
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in Neural Information Processing Systems, 2017.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8: 143-195, 1999.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but not shallow-netwond avoid the curse of dimensionality: A review. International Journal of Automation and Computing, 14(5):503-519, 2017.
Moshe Shimrat. Algorithm 112: position of point relative polygon. Communications of the ACM, 5(8):434, 1962.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory, 2016.
Carsten Thomassen. The Jordan-Schönfiee theorem and the classification of surfaces. The American Mathematical Monthly, 19(2):116-13 1992.
Helge Tverberg. proof the Jordan curve theorem. Bulletin of the London Mathematical Society, 12(1):34 38, 1980.
Roman Vershynin. Memory capacity of neural networks with threshold and ReLU activations. arXiv preprint 2001.06938, 2020.
Ming-Xi Xi Wang and Yang Qu Approximation capabilities of neural networks on unbounded domains. arXiv preprint vrXiv:/90.009200 2019.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference Learning Theory, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks powerful memorizers: a tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, 2019.

---

Published as a conference paper at ICLR 2021
Appendix
We first provide proofs of upper bounds in Theorems 1, 3, in Appendix A. In Appendix B, we provide proofs of lower bounds in Theorem 1, 3 and proofs of Lemmas 5, 6, 7 used for proving the lower bound in Theorem Throughout Appendix, we denote the coordinate-wise RELU by a and we denote the i-th coordinate of an output of function fx) by (f(z)).
A PROOFS OF UPPER BOUNDS
A. PROOF OF TIGITT UPPER BOUND IN THEOREM 3
In this section, we prove the tight upper bound on the minimum width in Theorem 3, i.e., width- (max(d, d₂ + 1, dg))) RELU+STEP networks are dense in C(O0, 1| R&x). In particular, we prove that for any f E C(O, 1 1) for any > O, there exists RELU+STEP network f of width max (d, + 1, 1,dy) such that su (l/((x) - [()) I Here, we note that the domain and the codomain can be easily generalized to arbitrary compact support and arbitrary codomain, respectively.
Our construction is based on the three-part coding scheme introduced in Section 4.1. First, consider constructing a RELU+S network for the encoder. From the definition gK. one can observe that the mapping is discontinuous and piecewise constant. Hence, the exact construction (or even the uniform approximation) such STEP (recall its definition r 1 [ı: 0)). We introduce the following lemma for the exact construction yк- The proof of Lemma 8 is presented in Appendix A.4.
the encoder requires the use of discontinuous activation functions
Lemma 8. For any K E N, there exists a RELU+ layers such that f(x) = 9K (x) for all x E [0. 1].
network f IR R of width 2 and O(2
For constructing the encoder via RELU+STEP network of width d, + 1, we sequentially apply чk to each input coordinate, by utilizing the extra width 1 and Lemma 8. Here, when we apply 9K to some coordinate (requiring width 2), we preserve other coordinates by applying identity mapping (requiring width d, - 1) for constructing the encoder within width dz + 1. Once we apply dк for all
input coordinates, we apply the linear transformation Σd= 9K (I,) 2 (i-1)K to obtain the output of the encoder.
On the other hand, the memorizer only maps finite number of scalar inputs to the corresponding scalar targets, which can be easily implemented by piecewise linear continuous functions. We show that the memorizer can be exactly constructed by RELU network of width 2 using the following lemma. The proof of Lemma is presented in Appendix A.5.
Lemma 9. For any function f* RR + R. any finite set X R. and any compact interval I IR containing X, there exists a RELU network f IR - IR of width 2 and O(22)) layers such that f(x) f²) (z) for all x E and f(I) C [mnn (2)), max (x))..
Likewise, the decoder maps finite number of scalar inputs in Cd to corresponding target vectors in Ciyy Here, each coordinate of a target vector corresponds to some consequent bits of the binary representation of the input. Under the similar idea used for our implementation of the memorizer, we show that the decoder can be exactly constructed by a RELU network of width dy using the following lemma. The proof of Lemma is presented in Appendix A.6.
Lemma 10. For any dy, M N, for any > 0, there exists RELU network f R - I² of width dy and (22 layers such that for all E Ca,M
f(c) decode (c).
Furthermore, it holds that f(R) j0, 1
Finally, as the encoder, the memorizer, and the decoder can be constructed by RELU+STEP networks of width d- width 2, and width dy. respectively. the width of the overall RELU+STEP network ff is max + 1, d ). In addition, as mentioned in Section 4.1, choosing K, MM E N large enough so that w-- K) + 2 M < e ensures ||f - ol I E. This completes the proof of the tight upper bound in Theorem 3.
12

---

Published as a conference paper at ICLR 2021
A.2 PROOF OF TIGHT UPPER BOUND THEOREM
In this section, we derive the upper bound in Theorem 1. In particular, we prove that for any p [1, 00), for any I* [2 [Rd)), ), for any ε > 0, there exists RELU network of width max (dg + 1, d such that || - /llp S e. To this end, we first note that since s* E (RR,, Rdv). there exists continuous function f" on a compact support such that
If
Namely, if we construct RELU network f such that - fllp S 2. then it completes the proof. Throughout this proof, we assume that the support of f is subset of [0, 11 and its codomain to be [0, 1jdr which can be easily generalized arbitrary compact support and arbitrary codomain, respectively.
We approximate I' by a RELU network using the three-part coding scheme introduced in Section 4.1. We will refer to our implementations of the three parts as encode K (z), memor ize k and decode That is, we will approximate f' by RELU network
K.M
f == decode memorize K,M encode
However, unlike our construction of RELU+STEP networks in Appendix A.I, STEP is not available, ie., uniform approximation of ςк is impossible. Nevertheless, one can approximate qK with some continuous piecewise linear function by approximating regions around discontinuities with some linear functions. Under this idea, we introduce the following lemma. The proof of Lemma 11 is presented in Appendix A.7.
Lemma 11. For any de, K E N. for any y > 0, there exist a RELU network f Rd - R of width de + and O(2 layers and D,, C [0, 1 such that for all [0, 1]d. Dy,
f(x) = encode (2),
(D,)) <,, J(Dz) C [0, 1}, and f(R4, \ [0.1](=) = (1 (1-2dz where μ denotes the Lebesgue measure.
2d.K)
By Lemma 11, there exist RELU network encode of width d, + and D, C [0, 10 such that ((D,) < and
encode k (a) = encode (x) for all x E 1j DD
encode k (Rd \ [0, 1] k
(4)
We approximate the encoder by encode Here, we note that inputs from D, would be mapped to arbitrary values by encode Nevertheless, it is not critical to the error || - fllp as u(,,) < can be made arbitrarily small by choosing a sufficiently small y.
The implementation of the memorizer utilizes Lemma 9 as in Appendix A.I. However, f'(x) 0 for all x E IRd., [0, 1]dr, we construct RELU network memorize K.M of width 2 so that
m K.M encode k (TR [0, = (0)-
To achieve this, design the memorizer for Ca, using Lemma and based (4)
1 2d.K
memorizel Mnnorizek.M00 [emoriizekM(() otherwise
We note that such design incurs an undesired error that a subset of EK == [] - 2- _11] might be mapped zero after applying memorize K. Nevertheless, mapping Ex to is not critical the d, can be made arbitrarily small by choosing a sufficiently large K.
error || - fllp as μ(Ek)
We implement the decoder by a RELU network decode of width dy using Lemma 10 as in Appendix A.1. Then, by Lemma 10, it holds that decode ar R [0, 1]d, and hence, f(R+: C [0, 1/
13

---

Published as a conference paper at ICLR 2021
Finally, we bound the error || fllp utilizing the following inequality:
1f - fflle (L [1)( - fxx)13dxx) #
(1) f())(((a)) :
= -(oeneeveeeu [1((x)) - [())]lBdx JEUUD
- d2 +2 (m(Ex) + u(D,)) x sup
(x) - f(x))
=EEXUD,
d2(wp(2-K) -K]
(k-(222-)+-00) 2- (2-dak +7) x sup =E(00,1]4z
[1 sup xe(0.1/
II())))))))
(,(wp(2-k)+3 Mp (2 (2-
d2k +1) x
(x(( (d,) (d.))) =E(0,1]4z
sup
By choosing sufficiently large K, M and sufficiently small y, one can make the RHS smaller than e/2 as supzejo.11 (x))l < co. This completes the proof of the tight upper bound in Theorem 1.
A.3 PROOF OF THEOREM 4
In this section, we prove Theorem by proving the following statement: For any p [1, oo), for any f E (P,,, R,,, ), for any > 0, there exists a network f of width max(d, + 2, dy + 1} such that I| Sllp e. Here, there exists a continuous function I' E C(C, R&)) such that
If - 2
since for E (PC,, Rd). Namely, we construct network f such that f S 1. it completes the proof. Throughout the proof, we assume that the support of f' subset of [0, 1] and its codomain is [0, 1] da which be easily generalized arbitrary compact support and arbitrary codomain, respectively.
Before describing construction, first introduce the following lemma.
Lemma 12 [Kidger and Lyons (2020, Proposition 4.9)]. Let p R + RR be any continuous non- polynomial function which is continuously differentiable at some with p'(2) + O. Then, for any f" E CKC, Rdd,, for any > 0, there exists a network f K. Rdd x Rdd of width de + dy + such that for all K.
f(x) = (11(x), (2(2)), where [[y]()) z/100 S and 11v2(x) - ft (x) Se.
We note that Proposition 4.9 by Kidger and Lyons (2020) only ensures [1)2 - (x) S E; however, its proof provides ||y (x) x
0|100
well.
The proof of Theorem 4 also utilizes our coding scheme; here, we approximate RELU network constructions encode memorize K.M- and decode in Appendix A.2 by p networks. Using Lemma 12, for any ε >> 0, we approximate encode by network encode of width d2 + so that
lencode x (z) e
S for all x E 10, \ Dr
and encode K (10, 1)==) C [- We note that encode & (10, 1 c [-E1, + a1] ] is possible as encode K (R..) c [0, 1] by Lemma 11.
Approximating the memorizer can be done in similar manner. Using Lemma 12, for any compact interval Ig C R containing Cd, K. for any 82 > O, we approximate memorizek... by p network m K.M of width 3 so that
K.M memorize M (c) memorize
kM)( Se for all E Ca.
14

---

Published as a conference paper at ICLR 2021
and memorizek K (I2) E-E2, 1 + Eg]. We note that memorize K. possible as there exists memorizo K.M (i.e., RELU network) such that memorize K.M (In) C [0 by Lemma 9.
(I2) [-E2, 1 + Eg] is
For approximating the decoder, introduce the following lemma. The proof of Lemma 13 is presented in Appendix A.8.
Lemma 13. For any dy: M E N, for any E > O, for any compuct interval I C containing [o, 1]. there exists p network f + Rd of width dy + 1 such that for all E I,
(I((c) - decode h (c)llx Se.
Namely, f(I) C
By Lemma 13, for any compact interval Z3 R containing [0, 1], for any eg >> there exists a p network decode of width dy + such that decode & he (c) ( E3 for all E Cd.
and decode is (Ix) E (- ea)
We approximate f' by p network f of width max (dz + d, + 13 defined as
f == decodej memorize o encode
Here, for any 7 > 0, by choosing sufficiently large K, M, sufficiently large Iz, Iz. and sufficiently small E2 so that y (2 K) ) + M < 2/z and w decodee (w [ennriiee k. 2-
(E1) + E2) + E3 S z.2 we
have
(1 fx 1n and c(0.1))))(--111 1 21 =0
sup
cl
(5)
where w iaanorize and w dacodaj defined on Ig and Iz, respectively.
Finally, we bound the error || fllp utilizing the following inequality:
(VoNEe 11 (10(x)) fx))1Bdd
11 - fllp ffl
- f(=)][dxx+ + S 11f(()) - - 1f((x)
[=) f(x) ((D4) x sup 1f((z) - f(x)) [f=))) zED,
sup \E
1/2
(1'(z)) s(x) +
[1)' + sup 11 #
sup AP
sup zE|0,114s
By choosing sufficiently small 1 E2, E3, 7, sufficiently large K, M, and sufficiently large Iz. Ig. one make the RHS smaller than e/ due (5) and the fact that supze/o.144 (I)(()))lp < xo. This completes the proof of Theorem 4.
A.4 PROOF OF LEMMA 8
We construct f + R as f(x) = f2x fi( where each fc : R - E is defined for x E [0, 1] as
fe(x) = (e ((-1)) 1) x x- K
if E (l - x ex2- k)
if [L - 1) x x
12x2-
ges g02 (z)
15

---

Published as a conference paper at ICLR 2021
where ge1 RR RR, 9t2 R R and ges IR? - R are defined as
(n(x): (o(x), a(r - 0)) gr2(2,2) (o(x 2), -0 - 1+)
ges(2,2) o(x + 2) + f..
This directly implies that f(z) 9K (z) for all [0, and completes the proof of Lemma 8.
A.5 PROOF OF LEMMA 9
Let [ = N and ( ....., (N) be distinct elements of X' in an increasing order, i.e., x < x(0) if i < j. Let x(() == min I and x(N+1) = max I. Here, (:))) < x:(1) and x(M) I (N(+1) as X C I. Without loss of generality,
assume that (o) 0. Consider continuous piecewise linear function
ft (xx(0) (N++)) - R of N + linear pieces defined as
((((1))
if E [x(0), ,x!1))
(((x): = (2(10)) + (2x0+))) (x((N)
(1 x(1)
if E [x(0), (((1))) for SiSN-1- if [x(N), (e(M)x((N+1)
2(111)2(0))
Now, we introduce the following lemma.
Lemma 14. For any compact interval I C R. for any continuous piecewise linear function f + R with P linear pieces, there exists a RELU network f of width 2 and O(P) layers such that f f()) for all x I.
From Lemma 14, there exists RELU network f of width and O((x1) layers such that f'(x) = f(x) for all E X. Since C [a((0,, x (N)+ = I and (Z) C min f (2), max (X)). this completes the proof of Lemma 9.
Proof of Lemma 14. Suppose that f is linear on intervals [min I, 21); x2), (x max I and parametrized
01 x x + by i E [min 2i)
02 + bz
i E x2)
(x)
0p x +
i E [xp-1 max
for some a,, b, E R satisfying a; X I; + b = a;+1 x Dz + b,+1- Without loss of generality, we assume that min 0.
Now, we prove that for any P 2 1, there exists a RELU network f : + R2 of width and O(P) layers such that (f(x)) = ax xr--1 and (f(=))2 (=) Then, (f(x)) is the desired RELU network and completes the proof. We use the mathematical induction on P for proving the existence of such f.
1, choosing (f(z)) = (xx) and (f(z)) a₁ (xx) + bj completes
the construction of f. Now, consider P > 1. From the induction hypothesis, there exists a RELU network g of width such that
(g(x))) o(x xP-2)
(1 x + b
if x E Inin if x E (21,
02 + bz
(o(x))2
aP-1 +
if [MP-2, max
Then, the following construction of completes the proof of the mathematical induction: f(x) = h2 a h1 g(())
hn (Ix z) = (o(x - xp-1
+ -p-1
= K) K)
h2(1,2) = (z, -ap-1-ap-2)
where K := min; minzez (a; b.). This completes the proof of Lemma 14.
16

---

Published as a conference paper at ICLR 2021
A.6 PROOF OF LEMMA 10
Before describing our proof, we first introduce the following lemma. The proof of Lemma 15 is presented in Appendix A.9.
Lemma 15. For any M N. for any O, there exists RELU network f R. - R² of width and O(2") layers such that for all x E [0,1] 11] MM.
[(x) = (yn (2))
where (x(x) qM(x), v2(x) 2dd x (x qar(())
(6)
and DM, = U - (ix2 0 M. Furthermore, it holds that
S(R) C 10. 2- x [0.
In Lemma 15, one can observe that Ca,M [0, DM for 5 2-d i.e., there exists RELU network of width 2 satisfying (6) on Ca, and (7). enables us to extract the first M bits of the binary representation of Ca.M. Consider outputs of g(c): (g(c)) for Cd, is the first coordinate of decode (c) while (g(c))2 E C(d,-1)4 contains information on other coordinates of decode (c). Now, consider further applying g to (g(c))2 and passing though the output (g(c))2 via the identity function (RELU is identity for positive inputs). Then, (g(((c))2)) is the second coordinate of decode (c) while (o(()(e))2), contains information on coordinates other than the first and the second ones of decode (c). Under this observation, if we iteratively apply to the second output of the prior and pass through all first outputs of previous g's, then we recover all coordinates of decode (c) within dy 1 applications of g. Note that both the first and the second outputs of the (dy 1)-th correspond to the second last and the last coordinate of decode, as (c), respectively. Our construction of is such iterative dy 1 applications of g which can be implemented by a RELU network of width dy. Here, (7) Lemma 15 enables us to achieve fR) C [0, 1]d, This completes the proof of Lemma 10.
A.7 PROOF OF LEMMA 11
To begin with, we introduce the following Lemma. The proof of Lemma 16 is presented in Ap- pendix A.10.
Lemma 16. For any da, any a E (0,0.5), there exists a RELU network f Rdd RRd= of width de + 1 and ((1) layers such that f(z) = (1...., 1) for all x E Rd \ |0,11 1]4, f(x) = for all [a, 14,1-a 1-11-ad4 a]d and (() c [0, 1]c.
By Lemma 16, there exists RELU network ha of width d, 1 and 0(1) layers such that hn (xr) (I.....1) 1) for all E dd= \ [0, 1]d=, h1(2) = x for all x E [a, a) ajd=, and h (Rd=) C [0, 1]ds Furthermore, by Lemma 15, for any > there exists RELU network g IR + R of width 2 and O(2*) ) layers such that g(c) gK (x(c) (c) for all c E [0. D (see Lemma 15 for the definition of DK.6).
We construct network h2 Rdd Rdd. of width de + 1 by sequentially applying g for each coordinate of an input x Rd,, utilizing the extra width 1. Then, h2(r) = 9x(x)) for all x e [0, 1] DK,,,d, where
DK.ddd := {x 1 :4; DK,s for some i}.
Note that we use qK( (x) for denoting the coordinate wise OK for vector æ.
Now, we define D. == ((0, 1] (a, 1 a)d+) UDK.d C [0, 1jd=, Then, from constructions of h1 and h2, we have
for all [0, 1] A,, h2 (x) 2 ,..., 2- for all dd [0, 1j
h2 hy (x) qkl (z)
ha (1) C [0, -
for all x E Dr
where we the fact that (1,...; 1) &Drrr DK,a,, and qx((1,.... 1)) (1 - 2-K ..... 1-2-K.
17

---

Published as a conference paper at ICLR 2021
Finally, construct RELU network f of width dz + 1-1a a
f(x) = Σ hh2 h1(2)), x2 x2
(i-1k)
Then, holds that
f(x) encodex (x)
for all [0, 1] Dr for all x R \ |000 1jd= for all Dy,
[(x) = 1 2d k
f(x) C [0, 1]
In addition, if we choose sufficiently small a and so that p(D,) < y, then f satisfies all conditions in Lemma 11. This completes the proof of Lemma 11.
A.8 PROOF OF LEMMA 13
The proof of Lemma 13 is almost identical to that of Lemma 10. In particular, we approximate the RELU network construction of iterative dy 1 applications of g (see Appendix A.6 for the definition of g) by a network of width dy + 1. To this end, we consider a network of width 3 approximating g on some interval J within a error using Lemma 12. Then, one can observe that iterative d, 1 applications of h (as in Appendix A.6) results in p network f of width d, + Here, passing through the identity function can be approximated using p network of width 1. i.e. same width to RELU networks (see Lemma 4.1 by Kidger and Lyons (2020) for details). Furthermore, since h is uniformly continuous on J, it holds that [lf(c) - decode (c))le S s for all E Cd,. and f(I) C [-E, + e|dy by choosing sufficiently large J and sufficiently small that wh( ( (ww (a) a) ...) S
e. This completes the proof of Lemma 13.
A.9 PROOF OF LEMMA 15
We first clip the input to be in [0, 1] using the following RELU network of width 1.
min max 0}, 1 = 1- a01- (z)
After that, we apply ge: : [0, + [0, 1]2 defined as
(ge(x)) ==
if E [0,2- -
8 2 M x (z 2-M -0 +6)
if (2-M 6,2-
2-M
if 2- 22
(ge(2))2
8-12 x (x - 2 2 + + -
if E (2x2- - (8)
(e - 2-M MM
if E [[e - 1) x 2 2
From the above definition of Gr. one can observe that (92M (x))2 9M (x)(z) for r E [0, 1] Dx.6- Once we implement RELU network g of width such that g(x) = 92 (x). then, constructing f as
I' f(x) = ((g(z))2, 2 x ((g(=)), - (9(2))2)
2 == min max 00.f2200.. 0}.1}
completes the proof. Note that as (g(x))2 I x = (g(x)); for all æ E [0, f(x) E [0, 2 2-M x [0, 1]. Now, we describe how construct gaar by RELU network. One observe that (x))2 = and
(ge+1(x)); min {e {Ex2- 2-M max (8 1--1--M M (a 2x2-M +6) + (e 1) x (xxxx-(--()))) ,c(()))
for all xr i.e., alternating applications of min and max(,,)) Finally, we introduce the following definition and lemma
We consider W/ J.
18

---

Published as a conference paper at ICLR 2021
Definition [Hanin and Sellke (2017)]. f R - By is max-min string of length L if there exist affine transformations hi...., hy such that
h(xx) = - (4), 22-2((1-1 (2(ha(x)) (1 1,
where each Tt. either coordinale-wiis max (:,)) or min
Lemma 17 [Hanin and Sellke (2017, Proposition 2)}. For any max-min string f* Rd, - Bd of length for any compact K. C IRd=, there exists a RELU network f RRd - R x Rd of L layers and width dæ + dy such that for all K,
f(x) = (y1 (x). (2)))), where (1(z) = and v2(x) f (x)).
We note that Proposition 2 by Hanin and Sellke (2017) itself only ensures y/ = f (x)); however, its proof provides 1/1
well.
From the definition of the max-min string, one can observe that (02Mr (x)) is a max-min string. Hence, by Lemma 17, there exists RELU network g of width 2 such that g(x) 92 (x) gas (z) for all x E D This completes the proof of Lemma 15.
A. PROOF OF LEMMA 16
Consider the following two functions from RR:
if - aa
h1 h1(2)=
1 (x a+
if E (1 a, 1)
if x 21
=o(1 o(1 s)/a)
i 5 i E (0, if a
h2(2)) =
[a x)
=1 - o0 o x)/a).
Using hi and h2, we first map æ Rd [0, 1 d= some vector whose coordinates are greater than one via g IRd + Rdd defined as
= rd, o 8d, ... 0T1 0 81
re(x) = (x 1) 10 h (x²)
st(x) = a + 1) 1 - 10 x h2(x1).
Here we use the addition between vector and scalar for denoting addition the scalar to each coordinate of the vector. Then, one observe that if x [a, 1 a]=,, then g(x)
and if x E RRd \ [0, 1]d,, then each coordinate of g(x) is greater than one. Furthermore, each re (or 8t) can be implemented by RELU network of width dz 1 (width d, for computing a 1) 1 and width one for computing h (x+)) due to (9). Hence, can be implemented by a RELU network of width dg 1.
Finally, we construct a RELU network f: Idd + Rd of width dN + 1 as f(x) == min {
min { (max(x; 0), 1} =1 o (z)))
Then, can observe that if [a, 1 a]d_, then f(x) and if Rd \ [0. 1Jd,, then f(x) = (1...., ...,,1) 1), and f f(Rd. c [o. 1]d= This completes the proof of Lemma 16.
19

---

Published as a conference paper at ICLR 2021
B PROOFS OF LOWER BOUNDS
B. PROOF OF GENERAL LOWER BOUND
In this section, we prove that neural networks of width dy 1 not dense in both (PC,, R24) and C(C, Rdv,, regardless the activation functions.
Lemma 18. For any set of activation functions, networks of width d, 1 are not dense in both (P(K,RR) and x.)).
Proof. In this proof, we show that networks of width dy - 1 are not dense in [,, RR)), which can be easily generalized to the cases of IP(K,, Bd and C(K,, IR4v). In particular, we prove that there exist continuous function f" [P( 1]d=, R and > 0 such that for any network f of width dy - 1, it holds that
|| - Allp 6
Let A be dy dyydimmesioonl regular simplex with sidelength v2, that is isometrically embedded into Rdv, The volume of this simplex is given as Vola, (4) Vd,+I We denote the vertices of this simplex by fuo...., Then, we can construct the counterexample as follows.
d,l
(x)
1/ (2d, + ()(4++1 v1)21 + (2i 2) - -2i 1)4441 if œ1 E
if 21 E
2d,
2d
for some
24+1
24+2
for some i
2dy
2dy
In other words, (xx travels the vertices of A sequentially as move 21 from 0 to 1, staying at each vertex over an interval of length 2d, +1 and traveling between vertices at constant speed otherwise, i.e., f is continuous and in L ((0, 1] ((=,
Recalling (1), one can notice that any neural network f of width less than dy and L 2 2 layers can be decomposed as tz g. where & R - Rd is the last affine transformation and denotes all the o...o oi f1. Here, we consider k = d, 1 as it suffices to cover cases h < dy 1. Now, we proceed as
preceding layers, i.e., 9 = 0L-1 o 1
(Nonia l1(())) (())) de
11f" fllp
Monna [f((x)) to o g((x) dz
Shatee inf 10.3/4 (2)ER")
(x) - 12(1" (x)) do
inf
max
inf l|u: t(u
2dl +
t: afline map iE (d, + af u
inf ||u; asllps HED ie(d,-1)a.E
inf
2dg + 1
where S denotes the set of all (dd--i)ddimmnioon hyperplanes in gd and [dy [dy ;= 10 d
As the vertices of A are dy+11 distinct points in general position, inf max +11 inf ||: agllp > O. To make this argument more concrete, we take volumetric approach; for any k- dimensional hyperplane H E Bddy have
Vol., (A) < Vola, (TH(
max inf ||, azl1a. rE(d, a.EH
Vole(S) denotes the volume of in the d-dimensional Fuclidean space.
20

---

Published as a conference paper at ICLR 2021
where THe denotes the projection onto H. As projection is contraction and the distance between any two points are at most v2, it holds that for any H.
Vola, (A)
max inf l1u, -a,l2 2 eel,,t1aa
2. -.Vol,,-1 -1 (1x E RRd
=10112
S $1})
v dy +1 2 dny
+ dy
2
1'
2
where T denotes the gamma function, and we use the fact that Vola, ({xr RR. || S 1)) 2 Volz,-1 (TH (A)) as A can be contained in a dy diydennnsional unit ball, and hence Tx(()) can be
contained in (dg 1)-dimensional unit ball. Thus we have Il fllp > E with
dy
dB
vd +1
dg +1
2
1
2 (2dg + 11 dy!
2
π
for p 2 and
8 Vdy
dy
+ 1
2
2 (2d, + 1) dg!
2
for p < 2. This completes the proof of Lemma 18.
B.2 PROOF OF TIGHT LOWER BOUND THEOREM
In this section, we prove the tight lower bound in Theorem 3. Since we already have the width-d, lower bound by Lemma 18 and is already proven that RELU networks of width de is not dense in ) (Hanin and Sellke, 2017), we prove the tight lower bound in Theorem 3 by showing the following statement: There exist f E C[O. 1]d, RR and = >> 0 such that for any RE RELU network f of width d, containing at least one STEP, it holds that
Ilf flloo > E.
Without loss of generality, we assume that f has d, hidden neurons at each layer except for the output layer and all affine transformations
are invertible (see Section 5.1).
Our main idea is to utilize properties of level sets of width-d,, RELU+STER networks (Hanin and Sellke, 2017) defined as follows: Given a network f of width de. we call a connected component of (v) for some y as level set. Level sets of RELU+STEP networks have a property described by the following lemma. We note that the statement and the proof of Lemma 19 is motivated by Lemma 6 of (Hanin and Sellke, 2017).
Lemma 19. Let f be a RELU+STEP network of width de containing at least one STEP. Then, for any level set S of f, S is unbounded unless it empty.
Proof of Lemma 19. Let l" be the smallest number such that STEP appears the f* layer. In this proof, we show that all level sets of the first l" layers of f are either unbounded or empty. Then the claim of Lemma 19 directly follows. We prove this using the mathematical induction on l". Recalling (I), we denote by fe the mapping of the first f layers of f:
Se oe e
a o 11
First, consider the base case: Et = 1. Assume without loss of generality that the activation function of the first hidden node in o is STEP. Then for any æ, the STEP activation maps the first component of f (x) to if (ta (x)); 2 0, and to 0 otherwise. This means that there exists ray R starting from x such that (R) [.) Hence, any level set of fi either unbounded or empty.
Now, consider the case that e" > 1. Then, until the (e* - 1) 1)-th layer, the network only utilizes RELU, Here, the level sets of fe- can be characterized using the following lemma.
Lemma 20 [Hanin and Sellke (2017, Lemma 6)]. Given RELU network 9 of width dz. let S C Rdd be a set such that x E S if and only if inputs to all RELU in g are strictly positive, when computing g(x)) Then, S is open and convex, g is affine on S, and any bounded level set of is contained in S.
21

---

Published as a conference paper at ICLR 2021
Consider S of fe--1 11 in Lemma 20 and consider level set T of fe- containing some 2, i..., T + 0. If x & S, then 7 is unbounded by Lemma 20. If x E S. we argue as the base case. The preimage of fe- (z) of the -h layer (i.c., ty-) contains ray. If this ray is contained in (S)), then T is unbounded as ft- 1 is invertible and affine on S. Otherwise, T S * 0 and it must be unbounded as any level set of ft- not contained in S is unbounded by Lemma 20. This completes the proof of Lemma 19.
Now, we continue the proof of the tight lower bound in Theorem based on Lemma 19, We note that our argument is also from the proof of the lower bound in Theorem 1 of (Hanin and Sellke, 2017).
Consider f [0. 1] + defined as
du Σ
2 2
(S .d, = i=1
Vi
Then, for a = and = O, one can observe that ( is a sphere of radius 1 centered at (b) = ((:..... }) Namely, any path from (b) to infinity must intersect with (a))- Now, suppose that a RELU+STEP network f of width d, satisfies that Il /l S Té. Then, the level set of containing (2 (2..... 2) must be unbounded by Lemma 19, and hence, must intersect with (J*)-'(a), (a). However, as 1 (f**)
1 and o (b)) 0, this contradicts with Il. Alloo I 16. This completes the proof of the tight lower bound max(d= + 1, dy) in Theorem 3.
B.3 PROOF OF TIGHT LOWER BOUND IN THEOREM
In this section, we prove the tight lower bound in Theorem 1. Since we already have the d, lower bound by Lemma 18, prove the tight lower bound in Theorem I by showing the following statement: There exist f E LP R) and > 0 such that for any continuous function f represented by RELU network of width d it holds that
|| - fl E.
Note that this statement can be easily generalized to arbitrary codomain. To derive the statement, we prove a stronger statement: For any RELU network f of width d,, either
L' H) or f=0
(10)
where f 0 denotes that f is constant function mapping any input to zero. Then it leads us the desired result directly. Without loss of generality, we assume that f has de hidden neurons at each layer except for the output layer and all affine transformations in f are invertible (see Section 5.1).
As in the proof of the tight upper bound in Theorem 3, we utilize properties of level sets of given by Lemma 20. Let S be set defined in Lemma 20 of f. By the definition of S, one can observe that Rd S # 0. Then, a level set T containing some x E IRdz ) S must be unbounded by Lemma 20.
we have fxx) 2 Y for all Here, if y == f(x)= > 0, then for == w (2),
x' E T' (a' d2d Ex T such that || 1 11100 S 53.
Since T' contains T which is an unbounded set, one can easily observe that (u(T) ) oo and hence, ST. [d()) co, i.e., f L" RR. One can derive the same result for fz)
Suppose that f=) = 0 for all x E Rd S. Then, f(x) 0 for all a E aS as S is open (see Lemma 20). Furthermore, we claim that f(S) {0} or f & LP(Rd=, RR. For any E S, consider any two rays of opposite directions starting from 8. If one ray is contained in and f E LRR RR,, then its image for f must be {0}. If the image of is not (0), using the similar argument for the case f(z) > 0 leads us to f & (P R). Then, one can conclude that f(s) = 0. both rays are not contained in S, they must both intersect with as. Then, since is affine S, [()) must be zero as f(aS) = {0)- Hence, we prove the claim.
This completes the proof of the tight upper bound in Theorem 1.
y denotes the Lehesgue measure.
22

---

Published as a conference paper at ICLR 2021
B.4 PROOF OF LEMMA 5
Let (xx) Ar + for some invertible matrix A [[11 [01,02] E IR2x2 and for some vectors
a1, 02 E R², Then, is easy to see that if
(11 x) + b1
and (az; x) b2 2 O,
i.e., I E S, then Φ o (xr = z. Hence, the first statement of Lemma 5 holds.
Now, consider the second statement of Lemma 5. Suppose that (a1, 2) + b1 2 but (az, 2) + b2 Then, one can easily observe that Ø o o o maps ray
fa' E R (01. x²) ()1, (a2, x²) + b2 < 0}
containing æ to a single point Φ 3 (((a), x) + b1, 0)). which is on äs. In addition, similar arguments
hold for cases that (a1, 2) + bj < 0, (02, x)) + b2 2 0 and (01 2) + bj < 0, (az, x) + by < 0. This completes the proof of Lemma 5.
B.5 PROOF OF LEMMA 6
We first prove the first statement of Lemma 6 using the proof by contradiction. Suppose that x' and & T' but x' is not in a bounded sath-componen of R²² T Here, note that x = x' E S for S defined in Lemma& 5. Then, there exists path P from x' to infinity such that P n T' 0. If C int then the preimages of P and T n int(S) under Φ o o o stay identical to their corresponding images, i.e., P and T i int(S) (by Lemma 5). This contradicts the assumption that in bounded path-component of TR2 AT. Hence, it must hold that P Ø int(S).
Let xxd & T' be the first point in P P nas in the trajectory of P starting from x'. Then, the preimage of contains a ray R starting from x" (see the proof of Lemma for the details) which must not intersect with T: had the ray R. intersected with T, then R E T must have mapped to x", which contradicts x" gf 'T' and the definition of P. Furthermore, from the definition of x", the subpath pi of P from x' to excluding x" satisfies pi iSt(S). Hence, the preimages of pi and T' n in)(S) under Φ a & stay identical by Lemma 5. This implies that there exist path 'pt from to x". and then path from x² infinity, not intersecting with T. This contradicts the assumption of Lemma 6. This completes the proof of the first statement of Lemma 6.
Now, consider the second statement Lemma 6. By Lemma 5, x + x' implies that x & and x' E as. Here, as the preimage of x' contains ray from x' containing æ, this ray must intersect with T from the assumption of Lemma 6. Hence, x' T and this completes the proof of the second statement of Lemma 6.
By combining the proof's of the first and the second statements Lemma 6, we complete the proof of Lemma 6.
B.6 PROOF LEMMA
Before starting proof, first introduce the following definitions and lemma. The proof of Lemma is presented Appendix B.7.
Definition 2. Definitions related to curves, loops, and polygons are listed as follows: For ld C R2 and F(U)= = {f E C((0, 1], R²): f
1)) = U..
li is a "curve" if there exists f E F(U).
is a "simple curve" if there exists an injective f F(U).
U "loop" if there exists f E F(U) such that f(1) = f(0).
l is "simple loop" if there exists f F(L) such that f(1) f0) and f is injective
[0, 1).
is a "polygon" if there exists a piecewise linear f E F(U) such that f(1) f(0).
(S) denotes the interior of S.
23

---

Published as a conference paper at ICLR 2021
22
-1
-2
-2
-2
42
3
2-
21
3-2-1
D
1-3-2-11111
(a)
(b)
(c)
Figure 3: (a) Illustration u. ge (g). (b) Illustration V, -6- (4). v. (c) Illustration of of ge- (4), v.
L is "simple polygon" if there exists piecewise linear f E F(U) such that -(1)= [(0) and I is injective on [0, 1).
Lemma 21. Suppose that ge- ((0,pi))nge- ((p2, 1]) = 0 and gr- (10, pi B is contained a bounded
path-component of I U for some U C ge- ((p2. 1]) U B. Then, ge- ([O, pıl) \ is contained in
bounded wath-component of R2 (ge- (p2. 12) BB.
In this proof, we prove that if ge- ((0, pil) n ge- ([22, 1]) 0. then ge- ([0, pıl) AB is contained in bounded componen of R² U for some simple polygon U c ge- ((p2, 1J) U B. Then, the statement of Lemma directly follows by Lemma 21.
To begin with, consider loop ge (Ip2, 1]) U C(ge- (P2), ge (1)) where L(x,r') denotes the line segment from x to x', i.e.
f(x, = (A x + (1 >) a' e [0, 1]].
Then, the loop consists of finite number of line segments, network is piecewise linear as well as L(ge- (P2), Dr- (1)). i.e., the loop is a polygon.
image of interval of a RELU
Since ge. ([22, (ge- (p2), ge- (1)) consists of line segments, under the assumption
f S
100 one can easily construct simple loop U in gr- ((P2, 1)) C(ge- (P2), ge- (1)) so that 2/ contains point the point (-1, then to point near the point (1, 1), and finally to the midpoint of [gge (p2). ge- (1)). We note that U/ also consists of line segments, i.e., U is simple polygon. Figure 3(a) illustrates l where line segments from ge- ([22, 1]) drawn in blue and line segments from [. (p2), ge- (1)) indicated by dotted black line.
simple curves from the midpoint of (ge-- (p2), (e-(())))
Now, choose g E (0, PI) such that (g) = =(0, (). Since - f1 S 100 and by the definition of (0,
e*
f(g) gr- (g) E for E R?? ||x - (0, ) S 100
which is illustrated by the red dot Figure 3. Then, we claim the following statement:
ge- (q) is contained in bounded path-component of R² U.
(11)
From the definition of and the path cath-connectedness of ge- ([0, 9]). one can observe that proving the claim (11) leads us that ge- ((0. q)) contained
bounded path-comppnent of IR2 A4 unless un ge- ([0, 4)) * 0. Since ge- ([0.pı)) \ B C ge- ([O, 4]) by the definitions of g. l and the assumption that ||S" ol S I this implies that if gr- ([0, pi.) n ge- ([p2, 1)) = then ge- ((O, pi]) [] B is
IOU contained in a bounded path-component of R22 \ U.. Hence, (11) implies the statement of Lemma
Proof of claim (11). To prove the claim (11), first introduce the following lemma.
Lemma 22 [Jordan curve theorem (Tverberg, 1980)]. For any simple loop O C R.? IR2 consists of exactly two path-components where one is bounded and another unbounded.
Lemma 22 ensures the existence of bounded path-component of R Au
Furthermore, to prove the claim (11), we introduce the parity function ny : RR2 1 + {0, For RR2 ll and ray starting from x, m=( counts the number of times that the ray "properly"
24

---

Published as a conference paper at ICLR 2021
intersects with U (reduced modulo 2) where the proper intersection is an intersection where Uz enters and leaves on different sides of the ray. Here, it is well-known that (z(x)) does not depend on the choice of the ray, i.c, Ty is well-defined. We refer the proof of Lemma 2.3 by Thomassen (1992) and the proof of Lemma by Tverberg (1980) for more details. Here, ty characterizes the "position" of x: as (x:) 0 if and only if is in the unbounded path-component of TR2 U4 which is known as the even-odd rule (Shimrat, 1962; Hacker, 1962). Hence, proving that Lu(ge (q)) = would complete the proof of the claim (11).
Recall that there exists the line (e.g.. the black arrow in Figure 3) that intersects with B and the image of ge- can be at only "one side" of the line (see Section 5.2 for details). Since B is open, there exists a "vertex" V E AB (e.g., the green dot in Figures 3(b) and 3(c)) such that is in the "other side" of the line. 12 We prove my (q)) = by counting the number of proper intersections between the ray R. from ge- ge-(4) passing through v (the red arrow in Figures 3(b) and 3(c) illustrates R.).
To simplify showing Mu(ge- (q)) = 1, we consider two points 21, 22 E U O ÖB near the points (-1,1), (1,1), respectively, such that the simple curve P in U from to 22 is contained in B except for 21, #2. Then, one can observe that P and ((2,, 22) forms a simple loop which we call V. Figure 3(b) illustrates V where the black dotted line indicates the line segment from [gee- (p2), ge- (1)), the blue line indicates the line segments from ge- ([p2. 1]), and the green dotted line indicates [(21: from the definition of P. the blue and green lines together correspond to P.
Then, (ge- (q)) = 1 as a ray from ge- (g) of the downward direction (the blue arrow in Figure 3(b)) only properly intersects once with V at some point in (ge. (p2). ge- (1)). under the assumption that fl I Tou From the property of sy, this implies that the ray R starting from ge- (g) and passing through v (e.g., the red arrow in Figures 3(b) and 3(C)) must properly intersect with V odd times. Furthermore, from the construction of 24 and V. definition of l" and under the assumption that Ilf" - fl S 100. one can observe that the simple curve in L/ from 21 to 22 not contained in B (i.e., 2t', \. P) can only intersect with B within the lxo balls of radius TOO centered at the points (-1, 1) and (1, This is because if U \ P intersects with B outside these &o balls, then by definition of t", the network cannot make further modifications in B, hence contradicting the approximation assumption ffl S 100:
1 In other words, all proper intersections between LI and R are identical
to those between V' and R. This implies that मय (ge- (q)) = 1 and hence, gr- (q) is in the bounded path-component of R2² \ U. This completes the proof of the claim (11) and therefore, completes the proof of Lemma
B.7 PROOF OF LEMMA 21
Suppose that ge- pI)) n ge- ((p2, 11) 0 and gr- ((0, \ B is contained in a bounded path- component of R22 LI for some C ge- ((p2, 1)) B. If ge- (0, \ B is path-connected, then the statement of Lemma 21 directly follows. Hence, suppose that ge- (iO, P1)) B has more than one path-components. To help the proof, we introduce the following Lemma.
Lemma 23. If ge (p) E 0B for some p E [0, 1). then f(p) = ge- (p).
Proof of Lemma 23. Suppose that f()) * ge- (p). Then, of o a orlge (p)) + gr- (p) for some
E>E". By Lemma 5, there exist 41, 02 E R and by, by E IR such that o; oo = x if and only
if (a),2) +b; 2 0, (a2, . +b2 2
Without loss of generality, we assume that (a1, ge- (p)) +6, 0.
Since ge- (p) E 0B, there exists = E B such that (a1, + bi < O, i.e., oe o a (v((2) A z, which contradicts to the definition of le by Lemma 5. This completes the proof of Lemma 23
By Lemma 23 and the assumption that 1 /1l S T0U ge- ([0, PI]) \ B can only intersect with 0B within the &oo ball O of radius 2
100 centered at the point (0, Hence, all path- wath-components of ge- ((0, p1)) \ B intersect with the line segment ØB n O. In other words, gr- ([0
\ B is in path-component of TR² \ (ge- ((p2, 1)) U B) unless ge- (Iz2, 11) intersects with 0B n O. However, by
Lemma 23 and the assumption that || fll < 100 ge- ([22, 1)) must not intersect with 0B n O.
This completes the proof of Lemma 21.
12 A vertex denotes one of the points (2,
25


Reviews:
[{"review_id": "bE0gaKjykHM", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper wants to establish tight theoretical lower-bounds on the minimum width required by a ReLU neural network to approximate \"almost all\" functions up to epsilon where the distance of approximation is defined using the Lp-norm. The paper improves the previously known bounds which lied in the range of d+1 and d+4 to exactly d+1. One of the results of this paper is to establish that this bound is exactly d+1 (I am summarizing the result while ignoring some precision/nuances). This result holds only when the distance is measured using the p-norm where p is finite. In the infinity norm setting, they show that this minimum width actually is indeed not a universal approximator. However, to ensure that the claimed minimum width also holds in the infinity-norm setting, they modify the activation functions to also allow for the threshold functions which is 1 if larger than 0 and 0 otherwise.\n\n\nThis is primarily a mathematical paper and the goal is to understand the minimum width required when arbitrary depth is allowed and thus, the results in this paper should be viewed as an interesting way to completely fill the full-understanding in the mathematics of deep neural nets. In general, the insights are unlikely to have any bearing on practice. With that disclaimer, here are my opinions of the paper. The paper provides a very interesting set of results. First, it fully solves the problem and gives exact bounds, where prior works have only given bounds that without getting the precise constants. Although one could argue that improving constants is not as significant, it still is important/interesting to learn that we can indeed find the precise constant (and arguably using a very nice proof/construction). Second, this paper also shows the dichotomy between approximation measured using Lp and L-infinity. In particular, there is no smooth transition between the minimum width required using only RELU activations between finite p and p-> infinity. However, it is also interesting that the fix to obtain the same minimum width is to allow for another additional activation function (and like RELU it is only non-differentiable at 0, Although, unlike RELU it is not continuous at 0 either). Overall the three set of results form an interesting and complete picture of the landscape for the required minimum width. The proof techniques involve viewing the mapping from input to output as a set of encoder, memorizer and decoder steps and implementing each of those using neural nets with RELU and optimal width. Combining the maximum of these widths gives the final required bound. I really like that the proof and construction is clean and simple to understand. Usually getting precise constants involves messy constructions; that is not the case in this paper and that is by far the biggest strength of this paper.\n\nI had a few suggestions on this paper, that I feel could make the results in this paper even better. \n\n- Even though the goal is to allow arbitrary depth, it is still instructive to add a discussion on the depth required in these bounds. In particular, what is the \"cost\" of having the width as small as the minimum required one, in terms of how deep the network should be, given a fixed error epsilon (or in terms of K, M if that is convenient)? \n\n\n- In the result for p -> infinity, is the number of step activations required optimal? It is clear that you would need some step functions, but how many? Currently you seem to require one for every input coordinate. Is this optimal? A discussion of this and its optimality will make the theorem/result more stronger. \n\n- It was not directly/quickly obvious to me how Lemma 8 + applying the q_K one for each input coordinate leads to a width of d+1 as opposed to 2d. The answer is that this is because you are mapping identity for all coordinates except one of them and repeating it d_x times. So stating this out, will make it quickly accessible to the reader. Even though this may seem \"obvious\", it improves the readability. \n\n- There seems to be a caveat that the neural net uses the target function itself in the construction of its weights. Although this proof is about \"information\" needed, a discussion surrounding this and/or explaining why this is okay will again make the spirit of the results clear to the reader.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NI-KYCBn_ia", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary: The authors tighten the analysis of the minimum width for universal approximation with relu networks for Lp functions, where they have an exact characterization in terms of the input and output dimensions.\n\nThe paper is well written and easy to follow. The review of prior art is quite clear. \n\nmajor comments/questions\n\n1. It appears that the main result on Lp functions can be seen as a generalization of Hanin and Sellke (2017)'s result for d_y=1 to arbitrary d_y. Could you contrast the main differences in the proof technique? \n\n2. It's interesting that uniform approximation is harder to obtain with relu networks, while relu+step works. However, step functions are not ideal from a practical perspective due to the a.e. zero gradient. Is there an optimization-friendly activation that satisfies uniform approximation with minimal width?\n\n3. Does 'relu networks of width m' refer to networks where the number of layers is arbitrary? Could you please clarify?  What is the minimum number of layers required for the results to hold? Are there any implications for relu networks of fixed layers, e.g., two and three layers?\n\nminor comments.\nTable 1. Ours (Theorem 2) has max(d_x+1,d_y), but isn't d_y=2 in this case?", "extra_scores": {}, "extra_text": {}}, {"review_id": "JCbVBm1Glq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of universal approximation with networks of bounded width and arbitrary depth. The objective is to understand what's the minimum width necessary to approximate any function in a suitable space. The main results of the paper can be summarized as follows:\n\n(1) ReLU networks approximate functions in $L^p(\\mathbb R^{d_x}, \\mathbb R^{d_y})$ if and only if the width is at least $\\max(d_x+1, d_y)$. This result is tight and improves upon (Kidger and Lyons, 2020), which give an upper bound of $d_x+d_y+1$.\n\n(2) The same result does *not* hold if we look at the approximation in $C(K, \\mathbb R^{d_y})$, $K$ being a compact. The author(s) prove that the minimum width is 3 by giving a counterexample. \n\n(3) In order to maintain the width of $\\max(d_x+1, d_y)$ in $C(K, \\mathbb R^{d_y})$, it suffices to use ReLU and threshold activations. \n\n(4) An upper bound on the width of $\\max(d_x+2, d_y+1)$ for approximation in $L^p(K, \\mathbb R^{d_y})$ is given for a wide class of activation functions. \n\n\nThe proofs contain two main elements of novelty: \n\n(a) The upper bounds (results (1)-(3)-(4) above) rely on what the author(s) call a 'coding scheme'. The input is mapped to a one-dimensional codeword by an encoder; the codeword is mapped to a one-dimensional target by a memorizer; and the target is mapped to vector close to the output by the decoder. The idea is that all these three maps (encoder, memorizer and decoder) can be constructed with neural networks of width $\\max(d_x+1, d_y)$ by using ideas of prior results, e.g., (Hanin and Sellke, 2017). The point of the coding scheme is to decouple the input and the output dimension: the original mapping from a space of dimension $d_x$ to a space of dimension $d_y$ is broken into (i) a mapping from dimension $d_x$ to dimension 1, (ii) a mapping from dimension 1 to dimension 1, and (iii) a mapping from dimension 1 to dimension $d_y$. This is what allows to improve the bound on the width from  $d_x+d_y+1$ to $\\max(d_x+1, d_y)$.\n\n(b) The counterexample on which the lower bound is based (result (2) above) comes from a topological argument. \n\nThe paper is well written, the results are interesting and strong, the proof techniques are novel. Thus, I am generally positive about the submission.\n\nI have a few questions/remarks:\n\n(Q1) This is a general question. The author(s) provide a general upper bound on the width of $\\max(d_x+2, d_y+1)$. Is that tight for a sub-class of activations? Any comment on how to improve it beyond ReLU?\n\n(Q2) Lemma 5. Does the set $\\mathcal S$ (or, equivalently, the choice of $a_1$, $a_2$, $b_1$, $b_2$) depend on $\\phi$? It looks like this is the case, and it would be better to clarify this point.\n\n(Q3) Section 5.2. It is mentioned that \"by the definition of $\\ell^*$ and Lemma 5, there exists a line intersecting with $\\mathcal B$\". How do you guarantee the intersection with $\\mathcal B$? The set $\\mathcal S$ in Lemma 5 is generic (and, in principle, may not give rise to an intersection). \n\n(Q4) In Lemma 6, the author(s) talk about a bounded path-connected component without defining what path-connected means.  \n\nI spotted a couple of typos:\n\n(T1) Page 6. \"memorizer_{K, M}\" should be \"memorize_{K, M}\".\n\n(T2) \"differentiable at at least\". This occurs several times in the main text and the appendix as well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DGaGc_6lRjG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==== Summary ====\n\nThe paper studies the minimal neural network width needed for universal approximation. While previous papers on the subject merely provided lower and upper bounds, this paper derives exact bounds on the minimal width. The paper considers both ReLU networks, as well as general activation functions, and examines approximation under both uniform norm and $L_p$ norm. In the case of functions with high-dimensional outputs, the derived bounds are better than previously thought ($d_x + d_y + 1$ to $\\max(d_x + 1, d_y)$), with possible implications to practical  network design.\n\n==== Detailed Review ====\n\nMain strengths:\n* The first exact bounds on the minimal width required for universal approximation, closing the gap between lower and upper bounds of previous results.\n* Significant improvement for the case of $L_p$ functions with multi-dimensional output, with possible practical implications. For encoder-decoder style networks, which are common in many vision and language tasks, prior results had suggested a width double the input dimension, whereas here it has been demonstrated to be sufficient to use the same dimension as the input (+1).\n* Show that uniform approximation with ReLU networks is slightly weaker than with networks with discontinuous activations (specifically, using both ReLU and step functions).\n* The results are very clearly presented, as are their comparisons to previous bounds, including a very intuitive proof sketch.\n\nMain weaknesses:\n* For the case of scalar $L_p$ functions, the previous \"gap\" was merely off by one, i.e., $d_x + 1 \\le w_{\\min} \\le d_x + 2$. In this particular situation, the improvement in absolute terms is quite minimal.\n* Even in the general case, the prior lower and upper bounds were already asymptotically tight.\n\nI recommend the paper be accepted, since the paper provides exact bounds that close the gap between lower and upper bounds, and that helps us understand these networks better. Although the gap has already been quite small in some situations, which might be regarded as incremental, in other cases, such as the very common encoder-decoder setting ($d_x = d_y$), the gap is large enough to affect practical considerations when designing compact networks. These improvements should be of interest to the general ML community.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two knowledgeable reviewers and one fairly confident reviewer were positive (7) about this submission. The authors' response clarified a few questions and comments from the initial reviews. The paper provides exact bounds that close the gap between lower and upper bounds, and that helps us understand these networks better. With the unanimously positive feedback, I am recommending the paper to be accepted. 
Decision: Accept (Spotlight)