Minimum width for universal approximation using ReLU networks on compact domain
Authors: Namjun Kim
Chanho Min
Sejun Park
Venue: ICLR 2024 poster (2024)
Keywords: universal approximation
neural networks
Primary area: learning theory

Abstract: It has been shown that deep neural networks of a large enough width are universal approximators but they are not if the width is too small.
There were several attempts to characterize the minimum width $w_{\min}$ enabling the universal approximation property; however, only a few of them found the exact values.
In this work, we show that the minimum width for $L^p$ approximation of $L^p$ functions from $[0,1]^{d_x}$ to $\mathbb R^{d_y}$ is exactly $\max\\{d_x,d_y,2\\}$ if an activation function is ReLU-Like (e.g., ReLU, GELU,  Softplus).
Compared to the known result for ReLU networks, $w_{\min}=\max\\{d_x+1,d_y\\}$ when the domain is ${\mathbb R^{d_x}}$, our result first shows that approximation on a compact domain requires smaller width than on ${\mathbb R^{d_x}}$.
We next prove a lower bound on $w_{\min}$ for uniform approximation using general activation functions including ReLU: $w_{\min}\ge d_y+1$ if $d_x<d_y\le2d_x$. Together with our first result, this shows a dichotomy between $L^p$ and uniform approximations for general activation functions and input/output dimensions.

Published as a conference paper at ICLR 2024
MINIMUM WIDTH FOR UNIVERSAL APPROXIMATION USING RELU NETWORKS ON COMPACT DOMAIN
Namjun Kim-
Chanho Min 2 AAoou University
Sejun Park
Korea University
ABSTRACT
It has been shown that deep neural networks of a large enough width are univer- sal approximators but they are not if the width is too small. There were several attempts to characterize the minimum width Wmin enabling the universal approxi- mation property; however, only few of them found the exact values. In this work, we show that the minimum width for L approximation of L functions from [0, 1041 dR exactly maxfdg. dyy 2] if an activation function is RELU- (e.g., RELU, GELU, SOFTPLUS). Compared to the known result for RELU net- works, Wmin max (dz + 1, dg) when the domain is IR our result first shows that approximation on a compact domain requires smaller width than on R We next prove a lower bound on Wmin for uniform approximation using general acti- vation functions including RELU: Wmin 2 dy + if dg < dy < 2d Together with our first result, this shows a dichotomy between L and uniform approxima- tions for general activation functions and input/output dimensions.
INTRODUCTION
Understanding what neural networks can or cannot do is a fundamental problem in the expressive power of neural networks. Initial approaches for this problem mostly focus on depth-bounded net- works. For example, line of research studies the size of the two-layer neural network to memorize (i.e.. perfectly fit) an arbitrary training dataset and shows that the number of parameters proportional to the dataset size is necessary and sufficient for various activation functions (Baum, 1988; Huang and Babri, 1998). Another important line of work investigates class of functions that two-layer networks can approximate. Classical results in this field represented by the universal approximation theorem show that two-layer networks using a non-polynomial activation function are dense in the space of continuous functions compact domains (Hornik et al., 1989; Cybenko, 1989; Leshno et al., 1993; Pinkus, 1999).
With the success of deep learning, the expressive power of deep neural networks has been studied. As in the classical depth-bounded network results, several works have shown that width-bounded networks memorize arbitrary training dataset (Yun et al., 2019; Vershynin, 2020) and can ap- proximate any continuous function (Lu et al., 2017; Hanin and Sellke, 2017). Intriguingly, it has also been shown that deeper networks can be more expressive compared shallow ones. For example, Telgarsky (2016); Eldan and Shamir (2016); Daniely (2017) show that there is a class of functions that can be approximated by deep width-bounded networks with small number of parameters but cannot be approximated by shallow networks without extremely large widths. Furthermore, width- bounded networks require a smaller number of parameters for universal approximation (Yarotsky, 2018) and memorization (Park et al., 2021a; Vardi et al., 2022) compared to Nepth-bounde ones.
Recently, researchers started to identify the minimum width that enables universal approximation of width-bounded networks as dual problem of the classical results: the minimum depth of neural networks for universal approximation exactly two if their activation function is non-pooynomial. Unlike the minimum depth independent of the input dimension de and the output dimension d, of target functions, the minimum width is known to lie between dz and d2 + dyy + a for various activation functions where a is some non-negative number depending on the activation function (Lu et al., 2017; Hanin and Sellke, 2017; Johnson, 2019; Kidger and Lyons, 2020; Park et al., 202 lb; Cai, 2023). However, most existing results only provide bounds on the minimum width, and the exact minimum width is known for a few activation functions and problem setups so far.
"corresponding author emails: namjun- kim @ korea.ac.kr chanhomin aaanhomi@@ajou.cc.k. sejun. wat..aaark00@@aal..ommm

---

Published as a conference paper at ICLR 2024
Table 1: A summary of known bounds on the minimum width for universal approximation. In this table, p E [1, oc) and all results with the domain [0, 1]d extends to an arbitrary compact set in Rd,,
Reference
Function class
Activation
Upper /owwr bounds
L' IR)
RELU
de + S Wmin S dg +
Lu et al. (2017)
RELU
W Wmin 2 dg
Hanin and Sellke (2017)
C(O0, 100,1
RELU
d₂ + W min S dg + dy
Johnson (2019)
C(O0, 1|0,
uniformly conti.
Wiin 2 dz +
([00,1].,13
conti. nonpoly."
Wmin I dg + dy +
Kidger and Lyons (2020)
C((0,1]4,,r3
nonaffine poly.
Wmin S d dy +
IP(Rd=, R4)
RELU
Wmin S d2 + dy +1
LP(R=, R$)
RELU RELU
Wmin = max + 1,
Park al. (2021b)
1(0,11)13)
Wmin > max + 1,
conti. nonpoly. Wmin S max + 2, d, +
LP(10,1]4,,44
Leaky-RELU
Wmin max dy 2}
Cai (2023)
arbitrary
Wmin max (ux dg)
C(
arbitrary
Wmin
max dg
Ours (Theorem
[2( R4y)
RELU
Wmin = max/11, dyy 2}
Ours (Theorem 2)
( 124)
RELU-LIKE
Wmin = max (22 dy, 2}
Ours (Theorem 3)
C([O, 1]d. Rd))
conti.
Wmin Z d, + 1d, <d, Sdd,
it
requires that a is uniformly approximated by a sequence of continuous one-to-one functions. requires that is continuously differentiable at least one point z, with a'(2) of 0.
$ includes SOFTPLUS, Leaky-RELU, ELU, CELU, SELU, GELU, SILU, and MISh where
GELU, SILU, and MISH require dg + dy 2
1.1 RELATED WORKS
Before summarizing prior works, we first define function spaces often considered in universal ap- proximation literature. We use C(X, to denote the space of all continuous functions from X' C TR y C IRd,, endowed with the uniform norm: ||] supzex [=] We also define y) for denoting the LP space, i.e., the class of all functions with finite I/-norm, endowed with the LP-norm: Il A (fx [1 where fdd denotes the de-dimensional Lebesgue measure. We denote the minimum width for universal approximation by Wmin- See Section 2 for more detailed problem setup. Under these notations, Table summarizes the known upper and lower bounds on the minimum width for universal approximation under various problem setups.
Initial approaches. Lu et al. (2017) provide the first upper bound Winin I dg + 4 for universal approximation of I.- (RL R) using (fully-connected) RELU networks. They explicitly construct network of width d₂ +4 which approximates a target L function by using de neurons to store the dg- dimensional input, one neuron transfer intermediate constructions of the one-dimensional output, and the remaining three neurons to compute iterative updates of the output. For cullti-dimensionall output cases, similar constructions storing the dg-dimensional input and dy-dimensio (interme- diate) outputs are used to prove upper bounds on Winin under various problem setups. For example, Hanin and Sellke (2017) show that REI.U networks of width dz + dy are dense C((O, 1Jd=, R&d,). Kidger and I Lyons (2020) also prove upper bounds on the minimum width for general activation func- tions using similar constructions. They prove Wmin S de +d, +1 for C(1, 1] (Rdv) if an activation function a is non-polynomial and o' (=) + 0 for some z, Wmin S dz + dy + 2 for C((O, (d)) a is non-affine polynomial, and Wmin S dz + d, + for [P(dd= Rd,) if RELU.
Lower bounds on the minimum width have also been studied. For RELU networks, Lu et al. (2017) show that the minimum width at least d, + and de to universally approximate ( and LP 1]d= Rdv,, respectively. Johnson (2019) considers general activation functions and shows that the minimum width is at least dg +1 to universally approximate C(10, 1 (R)v) an activation function is uniformly continuous and can be uniformly approximated by sequence of continuous and me-to--nee functions. However, since these upper and lower bounds have a large gap of at least dy 1, they could not achieve the tight minimum width.
2

---

Published as a conference paper at ICLR 2024
Recent progress. Recently, Park et al. (2021b) characterize the exact minimum width of RELU networks for universal approximation of ( R$) ): Wmin = max (dz + 1, dy). / To bypass width d₂ dy in the previous constructions and to prove the tight upper bound Wmin S max + dy), they proposed the coding scheme which first encodes a dz-dimensiooal input x to a scalar-valued codeword and decodes that codeword to a dy-dimensional vector approximating f(x) They ap- proximate each of these functions using RELU networks of width dg + 1, and max(dy, 2} as in previous constructions, which results in the tight upper bound. Using similar construction, they also prove that networks of width max(d, + d, + 1) are dense in L"((0, 1jd, RR,) if an ac- tivation function is continuous, non-polynomial, and o' (2) * for some E R. For uni- versal approximation of [[, 1jd² R using Leaky-RELU REEU networks, Cai (2023) characterizes Wmin = max(d2, dyy 2) using the results that continuous IP functions can be approximated by neural ordinary differential equations (ODEs) (Li et al., 2022) and narrow Leaky-REIUU networks can approximate neural ODEs (Duan et al., 2022). However, except for these two cases, the exact minimum width for universal approximation is still unknown.
One interesting observation made by Park et al. (2021b) is that RELU networks of width 2 are dense in (R, R²) but not dense in C( 1), R2). This shows a gap between minimum widths for L" and uniform approximations. Cai (2023) also suggests a similar dichotomy for leaky-RELU networks when d 1 and dy 2. Nevertheless, whether such dichotomy exists for general activation functions and input/output dimensions is unknown.
1.2 SUMMARY OF RESULTS
In this work, we primarily focus on characterizing the minimum width of fully-comnected RELU networks for universal approximation on compact domain. However, our results are not restricted to RELUU; they extend to general activation functions as summarized below.
Theorem states that width (ax dy: 2} is necessary and sufficient for RELU networks to be dense in (10, 1]6z, Rd Compared to the existing result that the minimum width is max (d++ max(d_ 1, 1,d when the domain is Rdd (Park et al., 2021b), our result shows a gap between minimum the compact and unbounded domains. To our knowledge, this is the first result showing such a dichotomy.
widths for L approximation
Given the exact minimum width in Theorem 1, our next result shows that the same wmin holds for the networks using any of RELU-LIKE activation functions. Specifically, Theorem 2 states that width max (dz, dy: 2} is necessary and sufficient for networks to be dense in L"([O, 1]d= Rd4)
if a is in [SOFTPLUS, Leaky-RELU, ELU, CELU, SELU), or is in {GELU, SILU, MISH} and d, + d, 2 3, which generalizes the previous result for Leaky-RELU networks (Cai, 2023).
Our last result improves the previous lower bound on the minimum width for uniform approx- imation: Wmin 2 dy + -1 for RELU networks if dz
1, = 2. Theorem 3 states that a networks of width dy is not dense in C(O0, 1]0= Rd) if dl < dy S 2d, and a can be uniformly approximated by sequence of continuous injections, e.g., monotone functions such as RELU.
For uniform approximation using Leaky-REL.U networks, the lower bound in Theorem 3 is tight if dy 2dz: there matching upper bound max(2d, + 1, d,y (Hwang, 2023). Further- more, together with Theorems 1 and 2, Theorem 3 extends the prior observations showing the dichotomy between L and uniform approximations (Park et al., 2021b; Cai, 2023) to general activation functions and input/output dimensions.
Our proof techniques also generalize to L approximation of sequence-to-sequenec functions via recurrent neural networks (RNNs). Theorems 24 and 25 in Appendix F show that the same wmin in Theorems 1 and 2 holds for RNNs. In addition, Theorem 26 in Appendix F shows that Wmin S max (dz, dy, 2} for bidirectional RNNs using RELU or RELU-LIKE activation functions.
1.3 ORGANIZATION
We first introduce notations and our problem setup in Section 2. In Section 3, we formally present our main results and discuss them. In Section 4, we present the proof of the tight upper bound on the minimum width in Theorem 1. In Section 5, prove Theorem 3 by providing continuous function fz : dd > R. with d, < d, < 2d, that cannot be uniformly approximated by a width-d, network using general activation functions. Lastly, we conclude the paper in Section 6.
3

---

Published as a conference paper at ICLR 2024
2 PROBLEM SETUP AND NOTATION
We mainly consider fully-connected neural networks that consist of affine transformations and an activation function. Given an activation function a R + E. we define an L-layer neural network of input and output dimensions dæ, dy E N, and hidden layer dimensions di,..., dt-1 as follows:
f A 11 o Ó1-1 t2 Φ1 o f1,
(1)
where te: Rd- + Rd is an affine transformation and Φe is defined as ée( Id,) = (oni))).,,,,,aaa for all l [L]. We denote a neural network f with an activation function a by a "o network." We define the width of f as the maximum over di,...,di--.
We say "o networks of width w are dense in C)), if for any f E C(X,3) and E > 0, there exists a a network f of width w such that II - I E. Likewise, we say a networks of width w dense in [)) if for any f E (2) and e > O, there exists
network of width w such that - S 6. We say "Wmin = w for a networks to he dense in C/) (or ('()")))) are
if a networks of width w are dense not. In other words, Wmiin denotes the width of neural networks necessary and sufficient for universal approximation in C) (or (X(,
((X))) (or (' but o networks of width
We lastly introduce frequently used notations. For n. E N. we use Hr, to denote the n-dimensional Lebesgue measure and [n] 2 {1...., nt. For E N and S C R", we use diam(S) supz, I|x-
2ll2. A set Ht C R is half-space if H = {x E IR a Txxx x + b 2 0} for some a E R (O.....0)) and b E R. A set P C R" is a (convex) polytope if P is bounded and can be represented as intersection of finite half-spaces. For f R" - RTm. f(z), denotes the i-th coordinate of ((x). We define RELU-LIKE activation functions (RELU, Leaky-RELU, GELU, SILU, MISH, SOFTPLUS, ELU, CELU, SELU) in Appendix A. For activation function with parameters (e.g., Leaky-RELU and SOFTPLUS), we assume that single parameter configuration is shared across all activation functions and it is fixed, i.e., we do not tune them when approximating a target function.
3
MAIN RESULTS
We are now ready to introduce our main results on the minimum width for universal approximation.
L approximation with RELU-LIKE activation functions. Our first result exactly characterizes the minimum width for universal approximation of [P([0, :Rdv) using RELU networks.
Theorem 1. Wmin = max(dy (dz, , dy. 2} for RELU networks to be dense in LP 11d,, ,IR.).
Theorem I states that for RELU networks, width max(da, dy. 2} is necessary and sufficient for universal approximation of (P 1jd=, 1..)). Compared to the existing result that RELU networks of width max(dz, dy.2] are not dense in L (Pdda R2)) if de + 1 > dy 2 2 (Park et al., 2021b), Theorem 1 shows discrepancy between approximating L functions [0, 1)d=) and on the whole Euclidean space (i.e., IRdx). Namely, a smaller width is sufficient for approximating I.P functions on a compact domain if dy + 1 > dy. We note that similar result was already known for the minimum depth analysis of RELU networks: two-layer RELU networks are dense in LP ((,, 1]d=, Rd,) but not dense in L (RR, .12.) (Lu, 2021; Wang and Qu. 2022).
compact domain (i.e.,
Although Theorem 1 extends the result of (Cai, 2023) from Leaky-RELU networks to RELU ones, use completely different approach for proving the upper bound. Cai (2023) approximates target function via a Leaky-RELO RELU network of width max(d,, 2y using two steps: approximate the target function by neural ODE first (Li et al., 2022), then approximate the neural ODE by a Lea network (Duan et al., 2022). Here, the latter step requires the strict monotonicity of Lea and does not generalize to non-strictly monotone activation functions (e.g., RFLUU).
To bypass this issue, we carefully analyze the properties of RELU networks and propose a different construction. In particular, our construction of a RELU network of width max(dz, dyy 2} that ap- proximates target function is based on the coding scheme consisting of two functions: an encoder and a decoder. First, an encoder encodes each input to a scalar-valued codeword, and a decoder maps each codeword to approximate target value. Park et al. (2021b) approximate the encoder with the domain & using a RELU network of width d, + 1 and implemented the decoder using a RELU network of width max (dy. 2) to obtain a universal approximator of width max (d, + d,
4

---

Published as a conference paper at ICLR 2024
for LP(R,,, (R)) By exploiting the compactness of the domain and based on the functionality
of RELU networks, we successfully approximate the encoder using a RELU network of width max(d,, 2] and show that RELU networks of width max dy. 2} is dense in (P, 1
The lower bound Wmin 2 max(dz, dy.2) 2} in Theorem 1 follows from an existing lower bound Wmin max d,) (Cai, 2023) and lower bound Wnuin 2 2. Here, the intuition behind each lower bound dz. dy. and 2 is rather straightforward. If a network has width d, - 1, then it must have the form g(Mx) for some continuous function g IRd,- + dy and M IR (d, (dd,-)xxd, 1)xds, which can- not universally approximate, e.g., consider approximating || Likewise, if network has width dy 1, then must have the form Nh(x) for some continuous function h IR + R and N E R2, (d,-1), which cannot universally approximate. Lastly, a RELU network of width 1 is monotone and hence, cannot approximate non-monotone functions. Combining these three argu- ments leads us to the lower bound max max(dz, dy. 2 in Theorem 1. We note that our proof techniques are not restricted to RELU; they can be extended to various REL.Ullkke activation functions.
Theorem 2. Wmin max (dy, dy 2} for &p networks to be dense in I [P,, 1] , Rdv) if E (ELU, Leaky- RELU,, SOFTPL.U,, CELU, SELU), or up E (GELU, SIL.U, MISH} and dz + dy 23
Theorem 2 provides that for ELU, Beaky-RELU, SOFTPLUS, CELU, and SELU networks, width max (dz, dly 2} is necessary and sufficient for universal approximation of T,, 1jd, TR,)), On the other hand, the minimum width of GELU, SULU, and MISH networks to be dense in [[, 1)x), max(dz, dy. 2] if dz + dy 2 In particular, Theorem can be further gener- alized to any continuous function P such that RELU can be uniformly approximated by a p network of width one on any compact domain, within an arbitrary uniform error. We present the proof for the upper bound Wmin I max dy. 2} in Theorem in Section 4 while the proof for the matching lower bound in Theorem and the proof of Theorem 2 are deferred to Appendix C and Appendix D.
We note that proof techniques casily extend to RNNs and bidirectional RNNs: Theorems 24 and 25 in Appendix shows that the same result in Theorems and also holds for RNNs. Further- more, Theorem 26 in Appendix F shows that Wmin & max dzz dy. 2) for bidirectional RNNs using ,I
any of RELU or RELU-LIKE activation functions to be dense in LP
Uniform approximation with general activation functions. For RELU networks, it is known that R24y) ) is greater than that for [P( ,) in general. This is shown by the
Wmin for C(O 1]d= 11]d=,144 observation in (Park et al., 2021b): if dz 1 and dy 2, then width 2 is sufficient for RELU networks to be dense in (P( 1] ). but insufficient to be dense in C(OO, 1Jd=, Rd)). However, whether this observation extends has been unknown. Our next theorem shows that a similar result holds for wide class of activation functions and dy
Theorem 3. For any continuous RR- + R that can be uniformly approximated by a sequence
of continuous injections, if du dy S 2dz, then Wmin 2 dy + for ip networks to be dense in C((O, .R.).
Theorem 3 states that Wmin 2 dy + 1 for 11, if dy E (dg, and the activation function can be uniformly approximated by sequence of continuous injections (e.g., any monotone continuous function such as RELU). This bound is tight for Leaky- networks if 2d, = dy together with the matching upper bound max(2d, + 1, d, on Wmin (Hwang, 2023). Combined with Theorem 1, this result implies that Wmin for RELU networks be dense in C(O0, 144) is strictly larger than that for L' LP((O, 1]2,, R²) if d₂ < dy < 2d,. With Theorem 2 and monotone RELU-LIKE activation functions, a similar observation can also be made.
We prove Theorem 3 by explicitly constructing a continuous target function that cannot be approx- imated by a ip network of width dy in a small uniform distance where y is an activation function that can be uniformly approximated by sequence of continuous one-to-one functions. In particular, based on topological arguments, we prove that any continuous function that uniformly approximates our target function within small error has an intersection, i.c., it cannot be uniformly approximated by injective functions, which leads us to the statement of Theorem 3. We present a detailed proof of Theorem 3 including the formulation of our target function in Section 5.
We lastly note that all results with the domain [o, 1]d- also hold for arbitrary compact domain IC C Rd= if the target function f" is continuous, then one can always find K such that I. C [- K, KJd, and continuously extend f" to [-K, K]d, by the Tietze extension lemma (Munkres, 2000). If f is I.P then approximate f" by some continuous function and perform the extension.
5

---

Published as a conference paper at ICLR 2024
T(
g(T5)
(22)
h(ua)
S3
T2
Ts
(((2))
(2a)
h((a))
{ul, 1/, u3, u4) C
h(ua)
f (24)
S₁
S₂
T4
f (=1)
9
((%))
Figure I: Illustration of our encoder and decoder when d₂ = 2, dy = 1 and k = 4. Our encoder first maps each element of {Tı, .........
} to distinct sealar codewords u1, Mi,..... 04. Then, the decoder h maps each codeword u; to h(4)) = (=;) for some 2; E TT;
. T
TIGHT UPPER BOUND ON MINIMUM WIDTH FOR IP-APPROXIMATION
In this section, we prove the upper bound Theorem by explicitly constructing a RELU network of width max (d2, dy. 2} approximating target function in L 1] 1R)). Since continuous functions on [0, 1 are dense in [[0, 1]4=, IR,v) (Rudin, 1987), suffices to prove the following lemma to show the upper bound. Here, we restrict the codomain to [0, 1] 1 however, this result can be easily extended to the codomain d since the range of f* C(O 1ja,, 1, R4) is compact.
Lemma 4. Let & > O, 22 1, and f E C(O0, 1jd= [0. 1]d,) Then, there exists a RELU network f: (0, 1]d= Rdv of width max (dz, 2) such that || fl
4.1 CODING SCHEME AND RELU NETWORK IMPLEMENTATIC (PROOF OF LEMMA
Our proof of Lemma 4 is based on the coding scheme that consists of two functions (Park et al., 2021b): the encoder and decoder. The encoder first transforms each input vector x E [0, 1]d scalar-valued codeword containing the information of then the decoder maps each codeword to target vector (0, 1 which approximates f (z). Namely, the composition of these two functions approximates the target function. The precise operations of our encoder and decoder are follows.
Suppose that partition , } of the domain [0, 1jdr is given. Then, the encoder maps each input vector in S; to some scalar-valuee codeword cs. Here, if the diameter of the set S; is small enough, then is reasonable to map vectors S, to the same codeword, say C E R, since the target function f is uniformly continuous on [0, 1] i... (z) f*(2') for all x' S,. However, since such an encoder discontinuous in general, we approximate using a RELU network via the following lemma. We present the main proof idea of Lemma in Section 4.2 and defer the full proof to Appendix B.3.
there exist disjoint measurable sets Ti...., . Tk C [0, 11 and RELU network f dRda - T of width max max(d,,) 2} such that
Lemma 5. For any a,
dT) S a for all [K].
na. (U Tr) 2 B, and
S(T.) {cz} for all [k), for some distinct CI...., R.
Lemma states that there is (approximate) encoder given by a RELU network g of width max (d. 2} that can assign distinct codewords to TI,..., Tg. Here, Tı.... Ty can be considered as an approximate partition since they are disjoint and cover at least 1 3 fraction of the domain for any 8 > 0. By choosing a small enough a, we can have a small information loss of the input vectors in Ti.... Te. incurred by encoding them via Lemma 5. We note that such an approximate encoder may map inputs that are not contained in Ti U... U TR to arbitrary values.
Once the encoder transforms all input vectors Te single codeword c; E R. the decoder maps the codeword a d, dindennnsil vector that approximates J" (T)().. We implement the decoder using a RELU network using the following lemma, which is a corollary Lemma Park et al. (2021b). See Appendix B.4 for its formal derivation.
Lemma in
Lemma 6.
For any p 2 1, 7.77 > distinct C₁ CI..... Cj E R. and Ui...., U2 E Rd, there exists a RELU network f [0, 1] of width max (dy, such that [[[(c)) villp Y for all E [k].

---

Published as a conference paper at ICLR 2024
H!
1(P)
N
R2
f1(7)
fi(T)
((C)
f(x)
Folh(T)
PnN
T
(a)
(b)
Figure 2: Construction of f in Lemma 7. (a) f preserves points in the half-space H represented by the gray area and projects points outside of H to the boundary of H (b) Illustrations of mapping T to a single point disjoint to P n Hi when du = 2: fi maps T onto the boundary of H and then f2 maps (T) to the point (2)(((T) while preserving points in P P n
Lemma 4 follows from an (approximate) encoder and decoder in Lemmas and 6. Let Ti,.... Te be an approximate partition and g be a RELU network width max dz. 2} in Lemma with some a, 3 > 0. Likewise, let h be a RELU network of width max dy. 2} in Lemma 6 with codewords Ck generated by g. 0; = (=:) for some 2; E T; for all i E [k)] and some 7 > O. Then, f = hog can be implemented by RELU network of width max dy 2] and can approximate the target function f error if we choose small enough a, 7. Since the codomain of our decoder is [0, 1]. one can observe that (x) E [0, 1J for any that is not contained in any of Ti,..., Tk. i.e., they only incur a small L error if 3 is small enough. Figure illustrates our encoder and decoder construction. See Appendix B.2 for our choices of a, B, achieving the statement of Lemma 4.
4.2 APPROXIMATING ENCODER USING RELU NETWORK (PROOF SKETCH OF LEMMA 5)
In this section, we sketch the proof of Lemma 5 where the full proof is in Appendix B.3. To this end, first introduce the following key lemma. The proof of Lemma 7 is deferred Appendix B.5 Lemma 7. For any d. E N, compact set K. C Rdd,, there exists a two-layer RELU network f + Rn of width dz such that
E Rd such that a a c > O, and b E R,
if x + 2
f(x)
x x-
Tot a
xc if + b<
Lemma 7 states that there exists two-layer RELU network of width de on a compact domain that preserves the points in the half-space H {x E Rd= a x + b 2 0} and projects points not in Ht the boundary of H++ along the direction determined by vector as illustrated in Figure 2a.
This lemma has two important applications. First, for any bounded set, Lemma 7 enables us to project onto a hyperplane (the boundary H()), along a vector c. In other words, we can use Lemma 7 for decreasing dimension of bounded set moving a point as illustrated in Figure 2a. Furthermore, given a polytope P C dd and a half-space H such that both P n H and P \ Ht construct RELU network of width d, that preserves points in P H and maps some T C P H with pa, (T) s Ad_ (P HC+ to a single point disjoint to P 2 H. As illustrated in Figure 2b, this can be done by mapping P H onto the boundary of H first, and then, iteratively projecting a subset of the image of P \ H+ (i.e., the image of T) to a single point using Lemma 7. We note that the measure of T can be arbitrarily close that of P H+ by choosing proper e in Lemma 7 when projecting P H onto the boundary of H
non-empty,
We now describe our construction of in Lemma (Si,..., S of the domain [0, 1]d, where each S; can be represented as
First, suppose that there is partition
S, = [0, 1] n (N
i-1 M5 n (H:))
for some half-spaces H ...., H the first image in Figure 3 for example. Suppose further that dSa < a for all E [k]. We note that such a partition always exists as stated in Lemma 10 in Appendix B.3. As in the second image of Figure 3, the most part of S (Ti in Figure 3) can be
7

---

Published as a conference paper at ICLR 2024
14g
S2
S3
S2
S3
T2
S3
0g
U2
S
S1
Ti
S₁
S4
11
Figure 3: Illustration of the encoder when de 2 and &o = 4. For each partition S; the encoder
maps C S; some point u, & {ui..... 14-1 } SH+1 U... Sk. After that, the encoder maps 2,...., to some distinct scalar values by projecting them.
mapped into single point (w) in Figure 3) disjoint to S2 U...UUS using Lemma 7. Likewise, map the Here, if U1 & H22 we first move it so that U1 E H2z using Lemma 7 while preserving points in S2 U....U U.. Sg. By repeating this procedure, we can consequently map the most parts (7I..... ... Tx) of SI....,oE St to distinct points via RELU network of width dz (the second last image in Figure 3). We finally project these points distinct scalar values as illustrated the last image Figure 3. See Lemmas 11 and 12 in Appendix B.3 and its proof for the formal statements.
part of S2 (T2 in Figure
single point disjoint to {ui US ....UU.. U.-
RELU network satisfies the three conditions Lemma The first condition is naturally satisfied since Ti C S; and (S, S a. The second condition can also be satisfied since the measure of T can be arbitrarily close to that S, for all i E [A:]. Lastly, our construction maps each Ti to distinet scalar value; this provides the third condition.
We note that our construction
5 LOWER BOUND ON MINIMUM WIDTH FOR UNIFORM APPROXIMATION
In this section, we prove Theorem 3 by explicitly showing the existence of a continuous function f [0, 1]d, + 12 that cannot be approximated by any o network of width d, within 1/3 error in the uniform norm when d, < dg S 2d,. Based on the following lemma, we assume that the activation function &p a continuous injection throughout the proof without loss of generality. The proof of Lemma 8 is presented in Appendix E.
Lemma 8. Let a R + be a continuous function that can be uniformly approximated by sequence of continuous injections. Then, for any network f [],1] + Rd of width and for any > O, there exists a yp network g :000001 1jdd - Rdd of width w such that up + R is a continuous injection and || g11=0 S.
Our choice of f". We consider f the following form: for r = dy - da, x = (21...., Fd,) E
[0, 104, 1 D1 = 1/3] and D2 = [2/3, 1]" x {1)d--7,
(1 6x, 6z2 .... :
G3 0,...00)
if E D
(w) 00, (......,, 6z - 5, 6.² ..... 6I, -5) if x E D2
(x)
otherwise
where g" is some continuous function that makes fr continuous; such g" always exists by the Tietze extension lemma and the pasting lemma (Munkres, 2000). We note that f'1p, and f D. injections whose images are [-1, 1]az {0}r and (0)d [-1, 1J", respectively, i.e., (D()) (D2 = (O,...,,)) }).. See Figures 4a and 4b for illustrations of Di, D2, f"( and (D2).
Assumptions o network approximating f". Suppose for contradiction that there
tinuous injection 9 IR + IR and a network f j0, 1]== dd such that I floo S 1/3 and tr Ø
to o t where t Rd. [R,,, t2, 12 + Rd, are some affine transformations and ø IRd, + Rdy is pointwise application of sp. Without loss of generality, we assume that t2...., tt are invertible, as invertible affine transformations are dense in the space of affine transformations on bounded support, endowed with || -lxo- Likewise, we assume that t is injective. Since &p is an injection, / also an injection, i.e..
f(D1) n (D2) =
(2)
However, one can expect that such f cannot be injective as illustrated in Figure 4c. Based on this intuition, now formally show contradiction.
8

---

Published as a conference paper at ICLR 2024
22
D2
(1.3)
99
(P5)
(4.0)
1" (3.4)
2/3
(,100,0)
V2
V2
(0
1/3
D:
(0.3)
1" (0.0)
((X)
(3-)))
(0,0,-3)
(a)
(b)
(c)
Figure 4: D1, D2 and their corresponding images of I when dz 2 and dy = 3 illustrated by the grey squares and red lines in (a) and (b). One of the possible images of f(D1) and s(D2) are represented by the grey surface and red curve in (c).
Proof by contradiction. Define h1 : 1-11, + Rd ho [-1,1] - R and sb: [-1,
[-1, 11,1 as follows: for a E 1111, [-1,1] and 7 (a, E [-1,1]
h1 (a) h2(33)
(1) [((a + 1)/6), h2( [(3
,,..,,,,, v(7) [h((a) - h12 (B)1lo
From the definitions of h1, h2 and Eq. (2), one can observe that
4 (1([-,, 1|4=) (2 = f(Di)
i.e. & is well-defined (and continuous) as (a) h2 (z) > for all (ax, E [-1,1]%, From the definitions of dp and the infinity norm, holds that
(i) 1|-1 C [] and
(ii) for each y E [-1, there exists E [dy] such that ((7), E {-1,1))
By (i), continuity of vb, and the Brouwer's fixed point theorem (Lemma 9), there exists y (a",8") E [-1,1] such that wx(")) = 7" Furthermore, by (ii), there should be E [dy] such that 7/- {-1, However, now show that such i does not exist.
Suppose that there E [dx] satisfying Y = --(");- = Then, by the definitions of f. hi, h2 and the assumption [|.f fllso S 1/3, the following holds for all = (z, y) [-1, 1]4 with Zi- = 1: hi (x);- E (-4/3 22/3] and h2(y)-- E [-1/3, 1 1/3). This implies that h1 (z))- h2()))
negative for all (ac, y) E [-1, and therefore, ('(>"); ;-- < 0 which contradicts v/(7")
1.
Using similar arguments, one can also show the contradiction for the two remaining cases: i E [dg]
and 7/-- -1; 1; and E [d,] [dz] and 7/- [1, In other words, 7f cannot be any of { {-1,
for all E [dyl- This contradicts (ii) and proves Theorem 3.
Lemma (Brouwer's 's fixed- fixed-point theorem (Florenzano, 2003)). For any non con-empty compact conver set K R2 and continuous function K. + K, there exists x E K. such that f(x") =x
6 CONCLUSION
Identifying the universal approximation property of deep neural networks is a fundamental problem the theory of deep learning. Several works have tried to characterize the minimum width enabling universal approximation; however, only a few of them succeed in finding the exact minimum width. In this work, we first prove that the minimum width of networks using RELU or RELU-LIKE ac- tivation functions is max dz, dy. 2} for universal approximation in []0 1] ). Compared to the existing result that width max{d,, + 1, d is necessary and sufficient for RELU networks to be dense in I.P 4R IR our result shows a dichotomy between universal approximation on a com- pact domain and the whole Euclidean space. Furthermore, using topological argument, we improve the lower bound on the minimum width for uniform approximation when the activation function can be uniformly approximated by sequence of continuous one-to-one functions: the minimum width at least dy + 1 if dg < dy < 2dz. which is shown to be tight for Leaky-ReLL networks 2d, dy. This generalizes prior results showing gap between L" and uniform approximations to general activation functions and input/output dimensions. We believe that our results and proof techniques can help better understand the expressive power of deep neural networks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
NK and SP were supported by Institute of Information & communications Technology Planning & Evaluation (IIP)) grant funded by the Korea government (MSIT) (No. 2019-0-00079, Artifi- cial Intelligence Graduate School Program, Korea University) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education
REFERENCES
Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 1988.
Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Yongqiang Cai. Achieve the minimum width of neural networks for universal approximation. In International Conference on Learning Representations (ICLR), 2023. 2023.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303- 314, 1989.
Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory (COLT), 2017.
Yifei Duan, Li'ang Li, Guanghua Ji, and Yongqiang Cai. Vanilla feedforward neural networks as a discretization of dynamic systems. arXiv preprint arXiv:2209. /0909, 2022.
Ronen Eldan and Ohad Shamir. The power depth for feedforward neural networks. Conference Learning Theory (COLT), 2016.
M. Florenzano. General Equilibrium Analysis: Existence and Optimality Properties of Equilibria. Springer US, 2003.
Boris Hanin and Mark Sellke. Approximating continuous functions by ReLU nets of minimal width. arXiv preprint arXiv: 1278, 2017.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 2(5):359-366, 1989.
Guang-Bin Huang and Haroon A Babri. Upper bounds on the number of hidden neurons in feed- forward networks with arbitrary bounded nonlinear activation functions. IEEE Transactions on Neural Networks, 1998.
Geonho Hwang. Minimum width for deep, narrow mip: A diffeomorphism and the whitney embed- ding theorem approach. arXiv preprint arXiv:2308. 15873, 2023.
Jesse Johnson. Deep, skinny neural networks not universal approximators. In International Conference on Learning Representations (ICLR), 2019.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on Learning Theory (COLT), 2020.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993.
Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An approximation perspective. Journal of the European Mathematical Society, 2022.
Zhou Lu. A note on the representation power of ghhs. arXiv preprint arXiv:2101.11288 2021.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
10

---

Published as a conference paper at ICLR 2024
James R. Munkres. Topology. Prentice Hall, Inc., 2000.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Conference on Learning Theory (COLT), 2021a.
Sejun Park, Chulhee Yun, Jacho Lee, and Jinwoo Shin. Minimum width for universal approximation. In International Conference on Learning Representations (ICLR), 2021b.
Allan Pinkus. Approximation theory of the mip model in neural networks. Acta Numerica, 8:143 195, 1999.
Walter Rudin. Real and Complex Analysis. McGraw- Inc., 1987.
Changhoon Song, Geonho Hwang, Junho Lee, and Myungjoo Kang. Minimal width for universal property of deep rnn Journal of Machine Learning Research, 2023.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory (COLT), 2016.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of ReLU neural networks. In Conference on Learning Theory (COLT), 2022.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2020.
Ming-Xi Wang and Yang Qu Approximation capabilities of neural networks on unbounded do- mains. Neural Networks, 2022.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. In Conference on Learning Theory (COLT), 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks powerful memorizers: tight analysis of memorization capacity. In Anmual Conference on Neural Information Processing Systems (NeurIPS), 2019.

---

Published as a conference paper at ICLR 2024
A DEFINITION OF ACTIVATION FUNCTIONS
In this section, we introduce the definitions of activation functions that we mainly focus on.
ReLU (RELU):
RELU(x) {0r
x if > 0 i
Softplus (SOFTPLUS): for >> O,
S)FTPLUS(I; log(1 exp(ax)).
LeakyReLUU (Leaky-RELLU) for (0,1),
if > if < 0 ax
Leaky- Lcaky-ReLU(x;aa)=
Exponential Linear Unit (ELU); for a > 0,
ELU(I;a) fwr (exp(x) 1)
x > 0 if <
Continuously differentiable Exponential Linear Unit (CELU): for a > 0,
CELU(Z; = x (exp(x//a) 1)
if > 0 if 0
Scaled Exponential Linear Unit (SELU): for A > 1 and a > O,
if > if
SELU(;; = (exp(x))-1)
Gaussian Error Linear Unit (GELU):
GELU(z) = x (zx)
where ((x) the cumulative distribution function of the standard normal distribution.
Sigmoid Linear Unit (SILU):
SILU(x) SIGMOID(z)
where SIGMOID(#) 1/ (1 exp(-x:) is the sigmoid activation function.
Mish (MISH):
MISH(I) = x x TANH(SOFFPLUSS(;; 1)) where TANI(Z) (exp(x) - exp(-x))((exp()) + exx((xx)).
12

---

Published as a conference paper at ICLR 2024
B PROOF OF UPPER BOUND IN THEOREM
B.I ADDITIONAL NOTATIONS
Prior to delving into the proof of Theorem 1, first introduce some notations that will be frequently employed in the subsequent sections. Given a set S C IK. int(S) denotes the interior of S and bd( denotes the boundary of S. For (a, b) E R" x R. H(a, b) - far E R" a x+ 0} denotes the hyperplane parameterized by and b. Likewise, we use H (a, b) far E Rd : a x + b 2 0} and H (a, b) - {z E IR" aT x + b S 0} for denoting corresponding upper half-space and lower half-space, respectively.
B.2 OUR CHOICES OF a. 3,7
0 so that (a) I E/21+1/p, B e² ((dy)) and y e/21+1/p. Here, Wp.2.5- denotes the modulus of continuity of f* in the p-norm and 2-norm: (x) - fr (x')ll, I (p2.1-(11x
We small enough
22) for all x, E [0, 10,= We note that such 2 is well-defined on [0, 1]. since I is uniformly continuous on [0, 1j (continuous function on com-
pact set). Namely, such a always exists for all s > O. Then, we have
/
1f f1ß
llf( ((=))=((>)lBduu
10
I
(If [(x)lEduds + JUL U: (x) -(x))
#
10, \ 1=1
U + +Σ/ / (11((z) (f(x)
S dg x Hdz
1=1
dg x 8 Σ / (1)f - (2)lle 11f(z) (r)llle)
S dy x 3 Σ / (wp.2 (1)))
+7)
S dy 8 (wp.2 (a) + +7)0 50
where 2; E Ti for i.
This leads us to the statement of Lemma 4.
B.3 PROOF OF LEMMA 5
We prove Lemma this section. To this end, we introduce the following lemma. The proof of Lemma 10 is presented in Appendix B.6. Here, H* (a, b) is defined in Appendix B.1
Lemma 10. Let Ko [0, 11". For any 8 > O, there exist mn E N and (a1, b1),..., (amzr bm) E R" R such that for Kc; = Ko n H where H = Ni= H+ (ag, by) for all i E [m]]
diam(Ko \ K1), dAC \ (K))..... d Km)) S 5 and Km = 0.
Lemma 10 ensures the existence of the partition (S S of the domain [0, 1j4 such that the diameter of each S; is upper bounded by given where each St can be represented
i-1
S, = [0, n (N (as, n (Ht (a:, b,)) #=1
for some (a1, b,),. .., (a,, by) E R x RR
To show the existence of approximation of partition {Ti...., T&> and RELU network of width max(d,. d,, 2} that maps Ti...., To to some distinct points, we introduce the following lemma. The proof of Lemma 11 is presented in Appendix B.7.
13

---

Published as a conference paper at ICLR 2024
Lemma 11. Let E, R be convex polytope and U1,.... ...,, Uk E R P be distinct points. Let H C I" be a closed half-space such that PnH + and P H + 0. Let m = max(n, 2}.
Then for any ó (0, 1), there exists RELU network f R mm of width satisfying the following properties:
[(x) for all x E EPNN
there exist distinct UI....;Uk E R (P such that f(ux) es for all i [k], and
there exist S P. Ht and uk-1 E R= \ (PP u (.1,..., vR3) such that (n(S) Z
0. (P(P) (H)) and f(S) {1k+1}.
Lemma 11 indicates that for each S,, there is RELU network g; of width max 2} such that 9: (i) preserves the points in S U U...U US. (ii) transfers the w1...., 04-1 (containing "information" that we want to preserve) some distinct points v1,..., 1/-1 not contained S:+1 U U.s. and (iii) embeds the most part of S; (i.e. T.) to the point v, distinct to existing points VI,.... 0 and also not contained in S U...U Sg. Hence, by repeatedly applying Lemma 11, we can find {TI,.... T and RELU network g of width max(d,, 2] such that Pn, (T:) (n((,)) B/k for all E [k] and the network maps each T₁ to Us E RT for some distinct UI...., Ug where m ma.
Lastly, we introduce the following lemma, which demonstrates the existence of a projection map that maps finite distinet points to some distinct scalar values. The proof of Lemma 12 is presented in Appendix B.8.
Lemma 12. For any 2 2 and distinct Ui Uk E R" there exists a' Ui...., a Ujs are also distinct.
R such that
By Lemma 12, there exists affine map h that maps u1,... un to distinct scalar values. Then, choosing f = h g completes the proof of Lemma 5.
B.4 PROOF OF LEMMA 6
In this section, we prove Lemma 6 by explicitly constructing the target f. As aforementioned, the proof of Lemma 6 is corollary of Lemma 9 and Lemma 10 in (Park et al., 2021b).
Before describing our proof details, we first introduce some functions introduced (Park et al., 2021b). quantization function Qn [0, 1] - Cn for n N and C, - {0,2-*, 2 2-,33 x 2-" 2-"} is defined as
qn (x) maxic C. c x),
an encoder encodex IR - Cd,KK K for some K E N is defined as encodex(x))
Σn i=l (x(x;) x (i-11)
gdy CM is defined
and decoder decodem: Ca.M -
decode (c) where
{0) = encode (c) nc
Namely, encodeg quantizes every coordinate of input up to K-bits and then concatenates whole co- ordinates into oneedmmenla scalar value. And, decode decodes one-dimensional codewords to diyddimessoonal codewords.
Now, we introduce the following lemmas presented in (Park et al., 2021b).
Lemma 13 (Lemma 9 in (Park et al., 2021b)), For any m E N, 0 S on < 02 <... < am S 1,
and 81, ..,....f 3m R, there exists RELU network f [0, + R of width 2 such that
f(a:) B, for all i [m].
Lemma (Lemma in (Park et al., 2021b)). For any dy, M E N, there exists a RELU network f: IR + gd, of width dy such that for any c Cd
f(c) (bi...., .a....,ba.) ba.)
14

---

Published as a conference paper at ICLR 2024
where bi....,buu buy CM satisfying [0, 1]dy
Eis by x 2 (1-1)_ Furthermore, it holds that f f(R)
Using Lemma 13, first exactly construct RELU network g of width which maps each code- word Gj to the corresponding encoded target vector encodeas (2;) Ca,. for some M E N; we will assign an explicit value M later. Next, by Lemma 14, we explicitly construct RELU network of width dy which maps each encodem to being the dy dyddieensio quantized target vector n! where oa = (v/......., 2 Vi and v/ = qM (Vs,)) for each j E [dy].
Let f be the composition of RELU networks g and h. That is, f is RELU network of width max 2). From the construction of g and h, the error between f(c,) v/ and e is only incurred from the quantization process. Hence, choosing sufficiently large M E N such that d x x2 M <n completes the proof of Lemma 6.
For the sake of completeness, we provide proofs of Lemma 13 and Lemma 14, which are from (Park al., 2021b).
Proof of Lemma 13. Consider the following piecewise linear function f :00, 1] + RR with m pieces which satisfies the statement of Lemma 13:
31
x E [0, 01)
Bi+1 Bg
f(z) =
Bi +
(xr a:))
a E [oa, 0541) for some E [m - 1]
0i+11 - ai
8m
if x E [am, 1]
From Lemma 15, construct RELU network f [0, 1] + R of width 2 satisfying f*(x) f(x) for all x E [0, 1]. This completes the proof of Lemma 13.
Lemma 15 (Lemma 14 in (Park et al., 2021b)). For any compact interval I C R. any continuous piecewise linear function f* C R with P linear pieces, there exists a RELU network f of width 2 such that f(x) (x) for all x E I.
Proof of Lemma 15. Suppose that f is linear P pieces [min I, 21), (21, ..., [IP-1, max and defined as
01 x x + bj
if E [min I,
0g by
if o [x1.
f(x)
up x + bp
if [-P-1, max Z]
for some 0; b, E RR satisfying assume that min I == 0.
x; b. di+1 T; bit Without loss of generality,
Now, we prove that for any P 1, there exists RELU network f I R² of width 2 such that f(x), = ReLU(z - x xP-1) ) and f(x)2 = (z). Then, the RELU network f(x)2 completes the proof. We use the mathematical induction for P prove the existence of corresponding f. When P= 1, choosing f(()) RELU(() and f(x)2 = a x RELU(x) + satisfies the desired property. Here, consider P 1. Then, from the induction hypothesis, there exists RELU network g of width
2 such that
((x) RELU(x xP-2)
01 x x bj
if æ [min I, x1) if x e [2),
0g x x + b2
9(x)2 =
0p-1 X x + bp-1
if x E [xr-2, max Z
15

---

Published as a conference paper at ICLR 2024
Then, the following construction of f completes the proof of the mathematical induction:
f() h2 o o hı g())
(z, 2) = (ar 1P----+ 2p-2; K)
0(x,z) (RELU()), RELU()))
h2(2,2) = (z, +
+ (ap +
ap-1) x x)
where K = min; minser(a x x b,). Hence, this completes the proof of Lemma 15,
Proof of Lemma 14. We first introduce the following lemma.
Lemma 16 (Lemma 15 in (Park et al., 2021b)). For any M E N. for any ō > 0, there exists RELU network of f RR2 of width such that for all x E [0, 1] M
f(x (y1 (z)),((()) where yn (x(x) q2s
y2(x) = 2M (a (xr(x)),
(3)
and DMs = U xix M - 8,ix2 M). Furthermore, it holds that
((R) C 00 2-- x [0.
(4)
Fix some d < 2- Then, Lemma 16 indicates that there exists RELU network g of width 2 satisfying (3) on Ca,M and (4) since Ca,M C [0,1] }]}] DM..- Such enables us to extract the first M bits of the binary representation of Cd. g(c)2 is the first coordinate of decode (c) while g(c)2 E Cd contains remaining information about other coordinates of decode (c). Therefore, if iteratively apply g to the second output the previous composition of and pass through all first outputs of the previous compositions of g, then we finally recover whole coordinates of decode (c) within dy compositions of y which can be implemented by RELU network of width dy. Moreover, (4) in Lemma 16 allows us to achieve f(R) C [0, 1]ds, This completes the proof of Lemma 14.
compositions of g. Our construction of such iterative dy
Proof of Lemma 16. First of all, we clip the input to be in [0, 1] using the following RELU network of width 1.
miax (z, 0}, 1) RELU(1 RELU(())
Then, we apply ge: [0, 1] + [0, 1]2 defined as
gr(x:)
if e 10,2-0 -8
12 x (x - 2-M +
if E e (2 - -,2-
2 M
if E [-M --2x2-M -d]
(e(x)²
8-12- M x - 2x2- 0) 2-M
if E (2x2 -,2 2 M)
(e ()-1) M
if E [(e 1) x 2-M M
From the definition of ge, one can observe that 92M (x)2 gM (x) for 00 Dar.s Therefore, once we implement G2 (z) using RELU network of width 2, and then constructing f
f(x) (g(2)2, 2 (g(2); - 9(()2))
z min maxx (z, 0}, 1) = RREULI - RELU(x))
completes the proof of Lemma 16. Now, we construct a RELU network of width which imple- ments J2M. One observe that 91 (Ir)2 0 and
96+1 (I)2 = min {e x 2 m 12- x (z- M + )) + (1 (6-1) 212 (((x))
for all x E (0, 1). To this end, introduce the following definition and lemma.
16

---

Published as a conference paper at ICLR 2024
Definition 1 (Definition 1 in (Hanin and Sellke, 2017)). f RR - Bd is max-min string of length 2 1 there exist affine transformations h hL such that
h(z) = - (a (b)(x)) m (12(2)), (x)))
where each Ty is either coordinate-wise max(:;)) or min(::).
Lemma 17 (Proposition 2 in (Hanin and Sellke, 2017)). For any max-min string f Rd Rd of length L. for any compact K. C Id,, there exists a RELU network IRd + IRda x Rdy of layers and width de + dy such that for all x E K.
g(x) = (11 U2(x),,
where V1 x and V2(x) = f(x).
Notably, G2 (x) is a max-min string so that there exists a RELU network of width 2 satisfying g(x)2 = 92 (x) = (x) for all x E [0. DM,5. This completes the proof of Lemma 16.
B.5 PROOF OF LEMMA 7
Let = fa....., and be basis of the hyperplane for E R" cJx = 0}, and let A =
[01, [01,...;ar) an] E R=xn Since a c + 0, invertible. Choose
K --1x min inf aj a
k (2....) sEk
and == Kb. K) E R". Then we claim that choosing
t)) f(x) = A (RELU(Az + -) -
completes the proof. Here, we use RELU for multi dimensional input by applying RELU element- wise. From our choice of A, v, and K, if a x 2 then f(z) x. Suppose that a x + b < O.
In this case, from our choice of K, the second to the last coordinates of RELU +v) are identical to that of Ax + v. Namely, we have
(a f(x) A- ((Ax + (aj b)e1) -)) x b)A--er
(5)
where (1, ... 0) I.. Since at 0 and at c= 0 for all i {2.... n). the first column of A- (i.e., e1) must be c/aj c/a" Therefore, by Eq. (5), it holds that
f(x) = a T +
x c.
a
This completes the proof of Lemma
B.6 PROOF OF LEMMA 10
The statement of Lemma 10 directly follows from repeatedly applying Claim 18. Specifically, we iteratively construct (aq,b, b,)...... and corresponding K1.... using Claim 18 so that diam(Ko K1), ... < 8 until diam(XC,) < 8 for some r E N. Then, we choose (ar+1. by41) such that
K = Kr n 7 (a,+1, brt1) 06.
Setting m + completes the proof.
Claim 18. For any > and bounded set Ro C R2 with diam(Ro) S D for some > 0, there exist is E N and (c1, (..,),...,,,,, d2) RR" x R. such that
diam(Ro) R1), ... diam (R R&) < 8 and
diam(R+) Z max D 00//(4
where R. RRnnni) H Ht( d,)) for all E [k].
17

---

Published as a conference paper at ICLR 2024
Proof. Without loss of generality, assume that Rg Bo where Bu denotes the n-dimensional
closed b2-ball of radius D/2. centered at the origin. In addition, we assume that D >> ó; otherwise,
the statement of Claim 18 trivially follows. retr= = V(D= //, 7 = D/2 T, U2 = - 2/||=112
for each x E bd (Bo), and S H (Uz: r). Then, we have
diam(Bo) \ ( S
(6)
Let B, be an n-dimensional closed fz-balls of radius D/2 7/2 > centered at the origin, i.e.. B1 C Bo Since Bo \ int(B,) compact and (TR" S x bil())) an open cover of
Bo int(B1), there exists a finite set I (B() such that
Bu \ int( C U (R" St
(R"
DEI
Let k = [ 1 Ib C. Uz and de = 7 for all i E [k]. Then by Eq. (6), it holds that diam(R,-1 \ R,) = diam (R, S I dio \ S s à
for all i E [k]. Furthermore, by Eq. (7) and Ry Bo, we have
R₂ = -Ro (U(R) (R" |(t)) c Bo (Bo int(Bi)) c Bi.
SEI
This implies that
D
vD 82
diam(R+) S diam(Bi) = D -- 2
S D
2
4D
where the last inequality follows from the concavity of the square root: Va - b S Va - b/(2/a
for a 2 O. This completes the proof of Lemma 10.
B.7 PROOF OF LEMMA 11
We first introduce the following lemmas.
Lemma 19. Let n. > 2, P C IR" be convex polytope, ......, E2 E R" \ P be distinct points, and Ht R" be closed half-space. Suppose that Z1,..., 71-1 E H and 2 2x Ht for some
1 E [k]. Then, there exists a RELU network f : R - IR" of width n satisfying the following:
f(x) = x for all x E.P
f(a))...., ffa).....ff$2.,. are distinct, f2; & P for all i [k)], and
E Ht
Lemma 20. Let 2, P C Rd be convex polytope, Ht C RR" be closed half-space such that PnH* * 9 and P *H* + V, and U1,..., Ug E H²* XP P be distinct points. Then for any 8 E (0, 1),
there exists RELU network f R + R" of width satisfying the following:
=(z)= all E (PNH+)u ( (o....., Uk).
there exist S C CPV H and vo4i E R" ((P (vi,...,ukk) such that Jrm (n((S) δ pn (P H+) and [(S) = (vR+I).
Z
Consider the case 2 2. By repeatedly applying Lemma 19, one can construct RELU network 9 of width n such that g (a) = x for x distinct. Let Then, one can construct a RELU network 92 such that (2)) = x for all x E (PnHttuufe,.... Up and (S) = (UL-1) for some uk+1 (P HT) U fei...., vx) and S C H with (S) 2
(1x) ) H+ \P, and gi (uI).... .., 91 (ut) 91 (u,) for all E [k]. Next, apply Lemma 20 to P. Ui...., Uk. and H
5 (P *)) Choosing f = 92 91 completes the proof.
For the case 1, the inclusion map 1 x + (z, 0) for x E R, we can also yield the RELU network f = 92 91 of width 2, which satisfies the statement of Lemma 11.
not directly apply Lemma 19 and Lemma 20. Nonetheless, by exploiting
18

---

Published as a conference paper at ICLR 2024
Proof of Lemma 19. Let 01 E R" \ {0} and b1 E R such that 7( for R" a. 0}-
Since P and } are disjoint closed convex sets, by the hyperplane separation theorem (Boyd and Vandenberghe, 2004), there exist 02 R" {0} and b2 E R such that
af 2 + b2
for all z E P and a 2 + b2 0.
(8)
Without loss of generality, we assume that d2 is not in the span of a1 Otherwise, we can consider a slightly perturbed version of a2 that is not in the span of a1 and achieves (8); such perturbation always exists since P and } are bounded.
Now, for E IR" \ {0} such that aj c > O, we apply Lemma 7 to construct RELU network fo of width of the following form:
if a x + b2
fc(x) r a tb
xc c
if a x b2 < <
ag c
Then, from our choice of 02, b2, and fer (i) fc(z) where
x for all
P. Furthermore, consider e S
a + bj
a x
0, 0,0 0)
S ERER \ {0):
a
x
02 प b2
02 r
Then, we have
a 21
b2
af [o(z)) +1 = aj
(1 c) + 20
20
02
where the inequality is from the definition of S and 0 + b2 < 0. In addition, for any R", it holds that aj fc(x) 2 a x. These inequalities imply that (ii) fe(2)).....fe
E H.*. P: if a a b2 2 0, then [=(z)) = 2i $ P
Furthermore, have (iii) Je(zi)....:: fe())
fe(P); otherwise, then a3 [z(2,) + b2 = 0 < 02 x + by = az fe( + b2 for all x E P. Here, one can observe that (S) 0 (i.e., S is non-empty) since a1 and ag are linearly independent.
Lastly, we show that there exists E S such that fe(z)..... fo(zx) are distinct. From the definition of fe and since 2; o zj for all i + j. fe(z;) = fo(z,) only if 2, 2j and are linearly dependent. However, the set of vectors that is in the span of 2 2j has zero measure with respect to pai however, (S) > O. This implies that there exists c E S such that fa(z), .., fe(2x) are distinct. By (i)((ii), choosing such e E S and f = fo completes the proof.
Proof of Lemma 20. Without loss of generality, we assume that the normal vector of the boundary of H is (I,0,... 0), i.e. we consider
HT= = H { (.1 Fa) R :1 + b1 2 0}
for some bj R. Let T (P U fur...... uk}.
min x, and H ((I1,,.., E RR" Is + by 20 bi = 1-1-1 (TT
for all i E [m] \ {1}. We note that by is well-defined since T is compact. Furthermore, from the definition of H.t holds that T < n H..
For y O, let K.,,, = Pn((a Hn) E R" 21 b + 7 S 0}. i.e., K, CP) H.S. Due to the continuity of Lebesgue measure, there exists a small enough 7"' >> such that frn (K.,.)) 5 (P HT)). Here, we choose S = K.,,. In detail, let = 1/n and consider corresponding K,,, and an indicator function Ix.,, Then, our choice 1x,,, is monotonically increasing on P H and converges almost everywhere on P HT to 1x, 1pptt- Then, by Lebesgue's Monotone Convergence Theorem (Rudin, 1987), Mr, (..) converges to nn, (P) Ht). Namely, we can choose N E N such that n., (K₂x)) 2 8 pm. \ Ht).
Let B, = (.),, |o:| for all i E [M] (1): each B, is finite since K,,- is bounded. Now, using Lemma 7, we construct a RELU network fi of width n of the following form: for (#1, (I,,..., E IR" and = (1, mmx (b2 + +2+ 1,1)/r" ..... max(b, Bn 1,,1//"))
x
i + b, 20 i + b <0'
[1(x) = { (x1 + b1)
19

---

Published as a conference paper at ICLR 2024
From the definition of fi, have fi(x) = n== H. for all E T. In addition, from the definition of Kyt, we have 21 + bj + Y" & 0 for all (Zi,..., [n) E Kgy This implies that fi (2)) -b, and
-x1 + b1) max (b, 3 + 1,11
f((x); 2,
S 24 max + 3: + 1,
B max
+
S s-b;- -1
for all i [n] \. {1} and for all a E Kyy Here, the first inequality from -(x1 + bi) 2 y"
and max + B, + 1,1] > O. We use B, 2 H; for the second inequality. This implies that Ji (Kg)))
H =0 0.
Now, we construct RELU networks ,n....;fn of width n using Lemma as follows: for (f1)...,,T) Rn) E R and i E (1).
f((x) x
if + 6, z; + b, <
(21...., 2;-1, -bs 2 Fn)
Here, one observe that fi(x) E Ni= H for all 7 and [n] \ (1). Furthermore, since (1() bb for all Key- and (K().))) ) n (U!h2 H
0, we have
fn . f2 fi( (-b), -b..... bn.) Since (-b1...., bm) $ T (e.g., min (I....... = b2 > -b2), choosing f = fn o o.... and U141 (-b),.... b,.) completes the proof.
B.8 PROOF OF LEMMA 12
Let Hij = fa E IR" x (w; - 0;) = 0) for < j. Then, a Ju,.... ... a uK are distinct if and only if & &Uics Hiz. However, since Hn (H.g) 0, we have u4 p4 (iic Hij) 0, i.e., there exists E R" \ (U1z) Myj). This completes the proof.
20

---

Published as a conference paper at ICLR 2024
C PROOF OF LOWER BOUNDS IN THEOREM AND THEOREM 2
We first introduce the following lemmas.
Lemma 21 (Lemma in (Cai, 2023)), For any activation function, networks of width max [2z d are not dense in both (K, Rdy) and C(C, I
Lemma 22. For any continuous monotone b, networks of width 1 are dense in L*((0, IR).
From Lemma 21 and Lemma 22, the proof of the lower bounds in Theorem and Theorem 2 directly follow.
Proof of Lemma 22. In this proof, show that for any continuous monotone v. there exists a L measurable function f [0, 1] > I that cannot be approximated by any d network of width 1, say f. within 1/6 error measured by L norm. Here, by the Hölder's inequality, suffices to show that I- 1/6.
Since any compositions of continuous monotone functions are continuous monotone, without loss of generality, we assume that &o network f is continuous and monotonically increasing function.
Consider f [0, 1] + defined as
i E 1 1 = So
(xx)=
if E (1/3,2/3)
and let f(2/3) for some R. Then i S.
10.1 Sol1 If fr
1f l
1f de 3
[1/3.2/3]
[1/3,2/3]
Likewise, c 2
| If - 50 dx 2
1f f do 2
11- 11-
[2/3.1]
12/3,1]
Furthermore, if (0,1),
1oar 10.11
- fd 2
1f f
1f f5-1"(dh
//3,22/3)
12/3,11
1
|c f' +
cc- 1z
- -
[1/322/3]
[2/3,1]
3
Hence, for any continuous monotone &p network can not approximate /" within 1/6 error, which completes the proof.
L
21

---

Published as a conference paper at ICLR 2024
D PROOF OF UPPER BOUND IN THEOREM 2
D.1 ADDITIONAL NOTATIONS
Throughout this section, use RELU-LIKE for the set of RELU-like activation functions of interest, defined as
RELU-LIKE (SOFTPLUS, Leaky-RELUU, ELU, CELU, SELU, GELU, SILU, MISH).
For E N and f R R. we denote (x)xx f ....o f the n-th iterate of the function f. For any continuous function on compact domain K. RR, Wp., denotes the modulus of continuity of f in the p-norm: [1f(z)) f(x')|lp I w ='ppp) for all x' E K. We note that such wp.f well-defined on a compact domain since f is uniformly continuous on a compact domain.
D.2 PROOF OF UPPER BOUND IN THEEREM
In this proof, we show that for any & > O, o E RELU-LIKE, and RELU network f width w, there exists tp network y with the same width such that
|/ gllp S.
Then, combining the above bound and the upper bound Wain S {dz, dy, 2} in Theorem completes the proof of the upper bound in Theorem 2.
To this end, we first introduce the following lemma. The proof of Lemma 23 is presented in Ap- pendix D.3.
Lemma 23. For any given compact set K. C and activation function E RELU-LIKE, there exists sequence } of networks of width such that it uniformly converges RELU K..
Lemma 23 states that for any given compact K. C IR, for each RELU-like activation function ço. and some fixed 8 O, there exist sequence {h₂} of sp networks of width 1 and N N such that [|ELU(<)) - (x) < on all 2 N and a E K;; we will assign an explicit value to å later. We note that suffices to show uniform convergence on an arbitrary compact set XC since functions of our interests are defined on compact domains.
Here, we denote a RELU network f as below, recalling (1):
= 1 o ΦL- .... 1200100
where L is the number of layers, te 1Rde-1 dd an affine transformation, and (2(2)...., (RELU(z)),.... RxLU((z))) for all é E [L]. And, for each RELU-like ac- tivation function yp, we choose y network g via applying the same affine maps ti....,te tt and h,, which is satisfying Lemma 23, such that
g t1 P..
where ... (h (x1).... ... hr (xar)) for all E [L]. We further denote fe and ge by the first é layers of f and g with the subsequent affine layer le, respectively:
ft -1-1 0 to and ge o p--1
22

---

Published as a conference paper at ICLR 2024
Then, for each & E [L] {1), have
[e - gellp = 114e Φ1- o fe-1 44 o pt- 9
I whep (1lor-1 fe1 pt-1 gr-1
S weew (1l0e-1 o fi- Φ1-1 ge + 1 - - ge-1o))
S whoo
||bc-1 se-1 - -1-1 ge-1ll
+ (V | 1 ( PC-1 o ge-1
1/8
|1be_ Se-1 P2-1 ge-1ll
whew
(Jo de
1/00
Σ - h=(ge-1(z))) duss
We note that Wt,pp is well-defined on [0, 1]d since t is uniformly continuous [0, 1jde. For each i 11. by Lemma 23, there exists N; E N such that
(RELU(gr-1xT)) hn 1 S
for all n 2 N; and x E [0, 1jdr Moreover, from the definition of de-11, we have
| ft-1 Φ1-1 o 9t-illp I - 9c-1ll S life-1 1 Di- 1i--
Therefore, for n 2 max/N1...... Nd. }. we have
|lōe-1 o fe-1 - 9--1llp life - gellp S Woo
*( de
1/2
RELU(go-1(E)) (aa)))-hnggg-- (1))) duis.
I whep (11fe-1 -6- + x d//1))
(9)
with Il.i 91 1p = ||t| tll1, = 0.
Consequently, by iteratively applying (9), we get
Ilʃ - allp S weL (1 - gr.-1lp x d//P)
S Wer (WL--I (l1f - g2-ellp + x d//i)) + d'/mm)
I Wii. Win (-- (-.. (llfi gillp + 8 d//r) ... ... 5 x 1/p
+ 5 1/p
d[-2
d[-1)
Wtr.P
Wh
... W... Whapp 8 d! (r)) ... 8 d 1/10 + x d //1
1-1
(10)
Thus, we can bound the right-hand side (10) of the above inequality within any > 0, by choosing sufficiently small 5 > O. Hence, it completes the proof of the upper bound in Theorem 2.
D.3 PROOF OF LEMMA 23
In this section, we explicitly construct a sequence of sp network { satisfying Lemma 23. Namely, show that for any 0. for any compact set K. R. there exists N E N such that (x)) RELU(z)] < = for all n 2 N and x E IC. Without loss of generality, we assume that K. [-m, M] for some m, M 0.
23

---

Published as a conference paper at ICLR 2024
1. xp SOFTPLUS:
In this case, we claim that hn (,) = (tg o p o t1)()) completes the proof for SOFTPLUS, where
t (z) and to (x) z/n. If z 2 0, by the Mean Value Theorem, have
1 Bn
(x) - Re) = 3n
log(1 + exp(Bnx))
log(exp(3nx))
3n
Otherwise, x < O,
1 log(1 (1 + exp(Bnar) 1
(x((2)) RELU(x)
log(2)
Bn
Bn
since SOFTPLUS is strictly increasing. Hence, choosing sufficiently large N E N such that 1/BN < &, which completes the proof for SOFTPIUS.
2. &p Leaky-RELU:
In this case, we claim that hn = 40 (x) completes the proof for Leaky-RELU. Here, from the definition of Leaky-RELU, we only consider for x < 0. Then,
I/a (1) (E) a" [r| S a" x m
We note that E 1). Hence, choosing sufficiently large N N such that aN x S which completes the proof for Leaky-RELU.
3. & ELU:
Similar to the case = Peaky-RELU we claim that (x) = (x) completes the proof for ELU and only consider for from the definition of ELU. Since ELU is bounded below by -a, strictly increasing, and (0) 0, we have
(x)] < a (x)) < a (1 - cxp(-a)) <a
[b)(r) < a(1
(1ecx((-)))) < a exp(-a))
We note that the upper bound of the sequence [/,, } is strictly decreasing and its infimum is equal to Thus, by the monotone convergence theorem, there exists N such that (z) (0E)U(=ELL()
(x)) S e for all n 2 N. Hence, this completes the proof for ELU.
80 CELU:
Since CELU is a smooth variant of ELU, the proof technique for CELU is the same as ELU. Consider (x) = (z)) Then, for < 0, we have
[z)( = h2(2)) < a(1 - 1/e) <a
hn((r) < a(1 - cxpp(1/e-1l)1 1)) < a(1 aa1-1/6 - 1/c)
Likewise, we note that the upper bound of the sequence h/ 1] strictly decreasing and its infimum is equal to 0. Thus, by the monotone convergence theorem, there exists N E N such that (x) RELU(x) = hh, (x)] S e for all N. Hence, this completes the proof for CELU.
5. 50 SEL.U:
From the definition of ELU and SELU, we can represent SELU as ELU. Hence, from the proof for ELU, (x) (tx o (p)"(z) completes the proof for SELU, where (x(x) = z/A.
y = GELU:
In this case, we claim that N., (x) = (l20g01, (x)) completes the proof for GELU, where 4 (x) and (2(x) = x x/n. If x 2 have
()) RELU(()) s01 *(nx)) cexp(_n2xx?p0 nye
since P(Z 2 t) < cxp(-t2 for all 0 where Z NO0 1). We note that the last inequality is derived from its derivative. Otherwise, if a < 0,
(x)(x) RELU(z) xd(nz) 1exp(_n222/11 n
24

---

Published as a conference paper at ICLR 2024
since P(Z < ( for all I 0 where Z ~ NO, 1). Hence, choosing sufficiently large N such that 1/N I E, which completes the proof for GELU.
7. y SILU:
In this case, we claim that (x) = (t2 ((poot)(()) completes the proof for SILU, where &1 f1(x) = na and (2()) = z z/n. If x 2 we have
exep(-111 (-na)
(p, RELU(=)]= =
1 + exp(cxxx) (nx))
exp(-10 nx.
1
< exeep(-nat I
Note that the last inequality is derived from its derivative. Otherwise, if < 0,
1
P (2) RELU(²)]= exp(-nxx) -
since x exp(-x) for all R. Hence, choosing sufficiently large N N such that 1/N < e, which completes the proof for SILU.
y MISH:
In this case, we claim that lo, (x) = (x)))))(()) completes the proof for MISII, where & (xx) nx and (2()) = x x/n. If 2 have
(9,(2)) RELU(x)] = (1
(1 + exp(nz))²-11
(1 + (xp(nx)) ) +
2x
1
+ exp(nx))) +1
exp(nar)
since 1 + S exp(x) for all x e R. Otherwise, if < 0,
(1 + exx((xx)))))))) -
(x)) RELU(x)]
+ exp )
(1 + cxp (xx) -1
S -
+ exp (nx)
- exeeppn2
Note that the last inequality is derived from its derivative. Hence, choosing sufficiently large N e N such that 1/N I c, which completes the proof for MISH.
25

---

Published as a conference paper at ICLR 2024
E PROOF OF LEMMA 8
In this proof, we show that for any >> 0, a that can be uniformly approximated by some sequence of continuous injection, say Pn, and network f of width there exists yn network g of the same width w such that
- - S..
From the assumption, there exists sequence of continuous injection {fn)) that uniformly converges a on R. Namely, for any 5 > O, there exists N N such that [l(,n()) - axx)l S for all N and E R; we will assign explicit value to å later.
Now, we denote a a network f as below, recalling (I):
f = o Ø1-1 .... o 12 o 01 1 where L E is the number of layers, te IR 61(011..., Ia,) (o(x1)..... ..,
Rdde an affine transformation, and for all & E [4]. And, we choose fpn network such that 9 Lr Pt-1 ........ 12 p1 o where pe( Fdd (x1)....... P.......... first é - 1 layers of f and g with the subsequent affine layer te, respectively:
(x )) for all E [L]. We further denote ft and ge by the
fe
11-1 00
and gt pe-1 p1 o
Then, for each & [L] (1). have
fe - gell 00lloo
= tt Φi-1 o fi-1 - t, o Pt-1 o g8-1ooo
I 00 (102-1 0 ft-1 Pt-1 92-1 10))
3 00 (10:-1 0 fe- 1 - 11-1 o -1- bo + | o ge-l pe-i o 96- 11)00
S 00
[1o1-1 o ft-1 - d:-1 o 9
+ sup zE(0,1]<s
|| 1 o ft- - Pi- PE-1 -
= o0 (lebe e se-1 - 1e- 11-11
sup max x sE|de-1
We note that o0 is well-defined on 1]4, since is uniformly continuous on [0, 1jd=. Since a is uniformly approximated by yo, for each E [d) there exists N; E N such that (1000))(z))) Pn ( 5
for all n 2 Nj and x E [0, 1| Therefore, for n 2 max(Na ,1,...,,,de..... we have
lefe gelloo S 00 (106_ fc-1 Φ:-1 1/-00
sup max (o( (x)00-12))))) =E(0.1]4s dE
S o0 (wer (Wor 1:00 ( 9l- (l,)) + +6) with [l silpp ||e, - ti llp O. Again, note that 1000 is well-defined on [0, 1jd, since p uniformly continuous [0, 1]dz.
(11)
Consequently, by iteratively applying (11), we get |l - glooo & W1,,00 (War_ (llf -L-1 1loc) +5)
I oiz,00 (woz 1:00 (wiz 1.00 (Woz 2.00 (11/2-2 -9L-21lo)) + 8)) +
< Wiz.o (Woz-1,00 (..- (Wis. (Waz (1lf2 92llz0) 8)) .... .). 8)
< 000 (Woz-1 (... (W'y (W (W (6)) + 6)) ... + 6)
(12)
Therefore, we can bound the right-hand side (12) of the above incquality within arbitrary e > 0, by choosing sufficiently small 5 0. Hence, it completes the proof of Lemma 8.
26

---

Published as a conference paper at ICLR 2024
F MINIMUM WIDTH FOR L" APPROXIMATION OF RNNS
In Theorems and 2, we prove the exact minimum width for I approximation via networks using RELU RELU-LIKE activation functions. Using similar proof techniques, investigate the minimum width for L approximation for other network architectures: recurrent neural networks (RNNs) and bidirectional RNNs (BRNNs) in this section.
F.1 ADDITIONAL NOTATIONS
We first introduce additional notations that will be used throughout this section. Given length T sequence of d-dimensional vectors x Rdx (i.e., æ matrix of rows and columns), we denote a token at index & E [2'] by x[t] E Rd (i.e., the 1-th column of x) and tokens from index 4 E [T] to l2 E [7] by x[l4 12] E [gdx(ta-(++)) for 4 l2 (i.e., the submatrix of consisting of its f f1-th.....t2 columns). We define recurrent cells used in RNN and BRNN architectures as follows.
RNN cell. A recurrent cell Rg of the layer & with hidden dimension d2 maps input sequence x = (=f11, x, x((T) E RdexT to an output sequence = [v[1]..... (((]) E Rd xT such that
ylt
Re(x)]( + se [z) + We2zltt 1]+
where 6e(01 Fdd) = (o(x))...... (xI,)) is a coordinate- wise activation function, and We,1, We,2 Rdxxd and be Rede are the weight parameters. The initial hidden state (z) is set to be 0 Rd,
BRNN cell. A bidirectional recurrent cell Re of the layer l with hidden dimension de con- sists of a pair of recurrent cells Re, Re with the same hidden dimension, and additional weight parameters Ae, B3 E Rdexdd such that
Re(x)[t o,
We be),
[t(x)[[-1 -
+ 1e bc),
1|1 + R (x) A A R. (x) [1] + (x)+())
where the initial hidden states ()) and [T)
set to be e
Network architecture. Given an activation function IR R. token-wise linear maps P : Rd - RdxT and Q: RaxT Rd,,x xT (i.e., there are some linear maps é Rd= -> Rd and vp Rd + Rdd such that [t))[t] ((x[t)) and (xx)[t) (x([t))), and L recurrent cells Ri...., Rr. with hidden dimensions di,..., dr, we define an RNN f as follows:
f Q Rr ....o R o P.
We denote neural network f with an activation function by a "o RNN" If we replace RNN cells R....., RS to BRNN cells R,...., Rr, then denote function f by a "o BRNN". We define the width of RNN (or BRNN) f as the maximum over dj di....,dd .,. dl.
We now introduce function spaces to universally approximate via RNNs and BRNNs. Given T N, we define the target function class LP(XTT .)T)), which consists of all L" functions with length T from X' C Rd to y C Rd, endowed with the entry-wise L'-norm: where || ||p.p is the Ipppp norm, i.e., entry-wise matrix norm. Unlike BRNNs, output tokens RNNs index & [T] only depend on æ t Rd_ We refer to such functions that only depend on past information as the past-dependent functions. Namely,
|| (Sxr [I
function f xdx Rdxx is past-dependent
f(x){t] g=(x[1:0
for some : Rd xt + da for all t E [T]. For a target function class for universal approxi- mation using RNNs, consider pest-dependent [ 1|d,x' Rd, XT), which is space of all past-dependent functions f such that f E [P( 1|= xT
xT) For target function class for
universal approximation using BRNNs, we consider TP 1 dxx RdyxT).
27

---

Theorem 25. For any T E N, Wmin = (dz, dy, 2} for &p RNNs to be dense in past- SOFTPLUS, CELU,SELU), or Published as a conference paper at ICLR 2024
Table 2: A known bounds on the minimum width for L approximation via RNNs and BRNNs using
RELU or RELU-LIKE activation functions. In this table, p E [1, oo) and all results with the domain [0, 1] extends 'T where I denotes an arbitrary compact set in Rd
Reference
Network
Function class
Activation o
Upper/ ppoer/lower bounds
RNN
L'(RREXT XT RRuxiyy IP R4
RELU
Wiin max + 1, dy Wmin S max (dz + 1, dg)
Song et al. (2023)
BRNN
RELU
Theorem 24
RNN
L L"([0, 1| 12
RELU
Wmin
max maxx(d2; dy: 2]
Theorem 25
RELU-LIKE'
Winin max ds dy, 2
RELU
Wmin max dn, dy 2
Theorem 26
BRNN
LP _|]_ ((0,))))x, [ddxx))
RELU-LIKE"
Wiinn max dz. dy, 2
requires the class consist of past-dependent functions. includes SOFTPLUS, Leaky-RELL and MISH requires dN + dy 2 3.
ELU, CELU, SELU, GELU, SILU, and MISH where GELU, SILU,
|| do not require dı + dy 2 3 for GELU, SIL.U, and MISH.
Before describing our results, we introduce a recent work for universal approximation of RNNs (Song et al., 2023). Song et al. (2023) show that the upper bound on the minimum width for universal approximation is independent of the length of the input sequences. In particular, they consider unbounded domain and prove that width max(d, + 1, d is necessary and sufficient for RELU RNNs to be dense in the past-dependent L (T x7, Rd, x7) and the same width max ddg + 1, d.y. is sufficient for RELU BRNNs to universally approximate LP xT Rd x.).
F.2 OUR RESULTS
We are now ready to introduce our results on a compact domain. The first result characterizes the exact minimum width of RNNs to be dense in past-dependent LP((0, 1]<=XT, IR RddxTT). The proof of Theorems 24 and 25 are presented in Appendix F.3 and Appendix F.4, respectively.
Theorem 24. For any T E N. Wmin = {dz, dy. 2) for RELU RNNs to be dense in past- [P([0, 1dxxT Rd,xT).
dependent [[0, 1]d= XT Rd,xT) if o E Pp (GELU, SILU, MISH) and d + dyy 23. 3.
Theorems 24 and 25 characterize the minimum width of RNNs using RELU or RELU-LIKE ac- tivation functions to be dense in past-dependent LP((0, []d,xT Rd:xTT is exactly max dy, 2). which coincides with the fully-connected network case (Theorems I and 2). Further, Theorem 24 shows dichotomy between the minimum width of RELU RNNs for L approximation the compact domain and the whole Euclidean space. A similar observation also holds for RNNs using RELU-LIKE activation functions using Theorem 25.
In order to prove the upper bound Wmin S (dz. dy, 2) in Theorems 24 and 25, we use coding- based proof techniques in (Song et al., 2023) but with different coding schemes (e.g., in Lemma 5). The lower bound Wmin 2 (dz, dy. 2} in Theorem 24 directly follows from the facts that for any
P (RELU) U RELU-LIKE and &o RNN f. fx)) Q R2 o Rí o P(x)[ is to network and Wmin 2 max(dz, dy, 2} is necessary for networks to be dense in LP R4) (Theorems 1 and 2).
Our next result shows that the same upper bound in Theorem 24 also holds for RELU BRNNs and BRNNs using RELU or RELU-LIKE activation functions. The proof of Theorem 26 is presented in Appendix F.5.
Theorem 26. For any T N and y (RELU) U RELU-LIKE, Wmin S (do, dyy 2) for ip BRNNs to be dense in TP TPP(O, 1) 1] x xT RdyxT).
28

---

Published as a conference paper at ICLR 2024
F.3 PROOF OF THEOREM 24
F.3.1 PROOF OUTLINE FOR RELU RNNS
In this section, we show that for any past-dependent f E IP([0, 1| RRAx)) and > 0, there
exists RELU RNN f [0, 1] xT + Rd x of width max(dz, dy. 2) such that
f E.
Without loss of generality, we restrict the codomain to [0, 1] XT Then, since continuous functions in C(O0, 1jd, xT xT) are dense in [[0 1]d,xT Rd,x?) (Rudin, 1987), it suffices to prove the following statement: for any > O, f' C( 1 1]d=xT, [0, 1j4,x)), there exists a RELU RNN f: x] + [0, x] of width max (dz, dy. 2) satisfying
|I flpp c.
We explicitly construct such RELU RNN using the coding scheme. To describe this, present the following lemmas where the proofs of Lemmas 27-29 are presented in Appendices F.--E8, respectively.
Lemma 27. Given T N and a, 3 > O, there exist disjoint measurable sets Ti...., Ts C [0, 1J and a RELU RNN g² 1]d.xT'"""" RR² of width max {d 2} such that
dT. < a for all i [k].
pd, (u Ti) 2 1 - 3, and
i E [0, Ijá.xT satisfies x|{] E for all & [T], then gl (x)[1) = c;, for all t [T), for some distinct C C R
Lemma 27 states that for any a. 3 > 0, there exist Ti...., ., Ts satisfying properties in Lemma 27 and RELU RNN g¹ of width max that assigns distinct codewords to each token æft] T, for t E [T]. However, unlike the fully-connected network case, the f-th token of the RNN output must be function of s=[1 8). To encode information of x: [1 t). introduce the following lemma.
Lemma 28, Given T E N and distinct CI,..., E R, there exist
distinct az for all j E [K]. and
a RELU RNN g² IRIxT' - IR 1xT of width 2 such that for any (Cig Crr.,.,,,r)))r......... with i....., ir E [k]
gx()][]]= = =a,
for all t E [T] where je (e))
Lemma 28 states that for any set of codewords .cI....,CH) there exists an RNN encoder imple-
mented by RELU RNN 9* of width 2 that maps any vector of codewords (ci...... Ci2) of length t E [T] into single scalar codeword ((i........) with the following property: different vectors are mapped to distinct scalar codewords.
By Lemmas 27 and 28, one can observe that for any a, B there exist .I...., Tk [0, 1Jd
a RELU RNN g' of width max(dz;2) 2}, and a, E for all j U?_,[k) [k]* satisfying the following properties:
diam(T)) I a for all [k].
pa, (U Ti) 2 1- 8,
aj az if [ i and
if e 00, 1] satisfies z(t] Tr, for all e [T], then g' (x)[t] a(j....)))
Namely, if Tr, .... Tey, then g' [1) ((Ii....t))
We construct RELU RNN that maps each (a())) ( (())....)))) to some y E RdxxT such that y(t] approximates (T, [1)) for all E [T].
29

---

Published as a conference paper at ICLR 2024
Lemma 29. Given T E N, p > 1, 7 > 0, distinct di,..., am R. and Ui..... Um R
there exists a RELU RNN h : R RIXT 7 [0, [0,1]4,* of width max 2} such that for any x (aj.....,((p)) with J1...., Jr [m].
[A(x)(t] Uge l1e S
for all t E [T].
By combining Lemmas 27-29, one can observe that for any a, 3, >> 0, there exist Ti...., [0, 1jd, a RELU RNN of width max dy, 2}. and vj E IR for all j E Ut=][k]' satisfying the following properties:
, Th c
dTi I for all E [M).
nd, (U Ti) 2 1 8,
i E 00, 10,1d satisfies x|{] E Ti, for all E [T], then
then
[l(())]] f' W(p (avT) (d,I33) 1
for E [T). and
i E (0, 1] satisfies x|[] & Tr, for some I [T], then f(x) E [0, 104xT
We will show that such RNN f of width max dey dy 2} satisfies ||f P'lpp S under proper choices of a, 8, > O.
F.3.2 OUR CHOICES OF a, 8,7 FOR RELU RNNS
We choose sufficiently small a > so that F,,. (av S E/21-1/p, 8 = ==//(2,, and
y e/22tt/p7T//) For convenience, use T T U Te. Under this setup, bound the error using the following inequality:
_ 11(((x) - (x)
|| f'
+ { (x) - ((p))lppppaee (13)
< T x sup 15EST 10.1)4xx777
[x)( - f (an)))))(((((tt))))
We first bound the first term in RHS of Eq. (13). Note that both f and f' have codomain is [0, 1]dy.
I
T x sup ETET D
[1((x)) - f(x) (I.))lppduaa
T
11- x (10, \T) x [0, 1111dx((11))
= T' x dyHarT
< Td
Md (T))
23 12/2.
(14)
". denotes the modulus of continuity I' in the nor- Frobenius-noma [f
f'(a))loo I W.r.)...r - for all x, E [0, 1
30

---

Published as a conference paper at ICLR 2024
We next bound the second term in RHS of Eq. (13) using Minkowski's inequality follows:
Jr. (1))))
-
Σ
EIM TI.
Σ
(x)) + [1f(x) - (z) Pduaet
II' The
Σ (KT
1/p
[f(())))) (1)
+ Tr,
1/p7
11(xz) - (1 Alee
1/8
Σ
(1(()))) - (2.
IT Ti,
E(KK]
1/87 P
Σ
11((x) - ( ) duace
IT
E
1/2
Σ
JTE- (W(P))) (llzzr - =]1=))² dpeet
(1... IIE Te,
1/77 v
Σ
Σ
[[f(x)] U/ lEdppto
II:m, The BE[T]
i [K]
1/v
Σ J
(WEeE (avT))" dfpaer
E(kk 112-, Tra
1/p P
{
Σ
/
[L...TEE 11221 Tr
$ (Wipp))) (aVT) + ) < EP/2
(15)
where 2fr E I Tr, for all i, [k). The second term in the above bound used our construction of Uj and f = h ot o gl. By combining Eqs. (13)-(15), we have
E Il f- -
S E.
2
2
This completes the proof of Theorem 24.
F.4 PROOF OF THEOREM 25
In this section, we prove that any RELU RNN (or BRNN) f can be approximated by an RNN (or BRNN) g of the same width using any of RELU-LIKE activation functions, within any uniform error. Note that a RELU RNN f of width w does not imply a RELU network with width w. Hence, need the following extended definition for analysis of RELU RNN.
31

---

Published as a conference paper at ICLR 2024
Given activation function R - R. define a token-network follows:
f21 2o...,,,.... FT) 1 1/2-1 ... 1he o 11,
(16)
where the is one of the following operations.
applying affine transformation t(-) on k-th token:
(1()),( (11, T2, .2..... rT) - T2, ( _.x))........................... .T) where W E [gdxdd b, Rd, æg E Rd and f(x) = War + be for some d, de N.
element-wise a activation on k-th token:
1h, (2,... XT) (2, .2...... (o(x))..........
where do is an clement-wise activation function.
copying the k-th token be to new token:
ee,k 02....,,................... ........................ TT) (311 , mkk)
IT,
adding two tokens with the same dimension into a new token:
(e.k,((11, .2...., .r) (I1, T2, Fr, I 21)
deleting k-th token:
(21, T2, FT) (x1, .2.... -. Tk+1 .TT
The width w of a token-network f is defined as the maximum of input/output dimensions of affine transformations that are applied in f. Remark that RNN (or BRNN) of width is a token- network with width w. If we define [|(=1.... .T.... l å supre(r] || can apply the same method in the proof of Lemma 8 in Appendix E. When d is either copying deleting, then
(x)(X) +b) < ||X YYloo
and when vb is adding tokens, then
s 2 Y (()()- +XY]l
above error bound holds.
So for given RELU token-network f, the following inequality holds for every db in f:
(X) ( S max - -Y
where M is maximum value norm of affine transformation ||ellooo in f. Therefore, using the identical method as in Appendix E, are able to construct RELU-LIKE token-network, y such that
ll g(x)l S.
Since uniform convergence of functions in compact domain implies p-norm convergence, we are able to extend the result of RELU RNNs RNNs using RELU-LIKE activation functions, hence the proof of Theorem 25 is completed.
F.5 PROOF OF THEOREM 26
In this proof, we follow the discussion in Appendix F.3. We use Lemmas 27 and 29 and a modified version of Lemma 28 to construct encoder and decoder BRNNs. The modified lemma follows: Lemma 30. Given T E N and distinct ci,..., R. there exist
distinct J. f.for all t E [T]. [k]', and je E [++ and
a RELU RNN g¹ IXT (1,..., E
x
XT of width 2 such that for any x. == (ci,...., Cir) with
32

---

Published as a conference paper at ICLR 2024
g0 (x)(t) ae..
for all 1 (T) where jt (f1,...,4h) it) and je = (fe:...,i7) iT).
Note that aj in Lemma 28 only depends the past whereas as... in Lemma 30 depends both the past and future. The proof of Lemma 30 is provided in Appendix F.9.
ready construct our BRNN model f. First, Lemma 27 ensures that there exist Ti...., Tk C 1j and RELU RNN g of width max 2}. Also from Lemma 30, there exist Jj R for all j.3 E U [k]* x [4]- [][t] j[0]. and RELU RNN g satisfying the following properties:
Now,
diam(Ti) S for all i [K]],
pa, (U Tr) 2 8,
"3 # 2 if (j.J) # J'), and
i E [0, 1]11] satisfies æ Tr for all E [2], then g og (x)[(f (4)
Namely, i Tú, X x Tir then g (x)(t] a6 ((66-..)))) Now, for given target function / E (10, 1] Rdxx)), we choose Zjr E II==1 Tr, as in Appendix F.3. Then, we define:
"). = f(
By Lemma 29, one can construct decoder h with respect to v. such that
|| J. 3. 7
Note that is a token-wise function that can constructed by a RELU BRNN. Then, the error bound Appendix F.3 indicates that for any have
If fllp.p SE
where f h' eg
Hence, using the extension of RELU token-network to RELU-LIKE token-network as in Ap- pendix F.4 completes the statement of Theorem 26.
F.6 PROOF OF LEMMA 27
To this end, recall the statement of Lemma 5: For any a, > 0, there exist disjoint measurable sets Ti.... Ts C [0, 1]de and RELU network IRd - of width max(d,,2) such that
dT, S for E [R).
pd. (U T:) 2 1 - 8, and
((T)) }c for all [k), for some distinct Ci...., Cb. R.
Therefore, the statement of Lemma 27 directly follows from token-wise implementing RELU network 9, that is, gi (x) = (..r())).....(((()))) for any x e [o, 1d,,7T xT
F.7 PROOF OF LEMMA 28
In this section, we explicitly construct RELU RNN f RIXT I satisfying the statement of Lemma 28. Without loss of generality, we assume that the distinct points cI...., are contained in [0, 1]. Then, we quantize each distinct point the binary representation using a token- wise RE..U network RR-. - R of width 2 such that for any K E N, > 0, and all x E [0, Dr.s.
g(x)
qι (z)
where DK - 2-xx-k - The existence of such is ensured from Lemma 16.
33

---

Published as a conference paper at ICLR 2024
Here, we recall the definition of the quantization function. A quantization function 9バ [0, 1] Cg
for K E N and Cк _ (0,2-K K 2- 2- ..... -2-*} } is defined
4x (x) maxfc E Cx c
One can observe that 9 preserves the first K-hits in the binary representation and discards the rest bits. Nonetheless, we can ignore the information loss, which is the duplication of points, incurred from the quantization by choosing sufficiently large K and small ó so that 2-(K+1 inl [ |eg Cy) and 8 < 2 2-(+2))
Subsequently, we implement a RNN cell R: IIXT + RIxT of width defined as follows:
R(x) 1] RELU(2-K K [())(t] xltt 1]).
Then, such R successfully accumulates (dz fi)-bits of the binary representation of 2|1 f) Rd for each E [T] since
<. [O, 1].
Lastly, let G R1xT + 1 be RELU RNN of width such that G(x) (g(x[1)), (T[) for all x E RdxxT Then, the RELU RNN = ft G of width completes the proof of Lemma 28.
F.8 PROOF OF LEMMA 29
From Lemma 6, there exits a RELU network g - [0, 1jdd of width max 2} such that for any p 2 1, 7 > 0, m E N, distinct 01,-.., a0 E R. and t1,,..., Um E Rdd,
(g(a;) usll, 5
for all E [m]] Therefore, the statement of Lemma 29 directly follows by token-wise implementing such RELU network g. that is, h(x) =
for any ......;Jr jr E [m].
F.9 PROOF OF LEMMA 30
In this section, follow the similar arguments in Appendix F.7 to construct RELU BRNN f: IR 1xT + R XX satisfying the statement of Lemma 30. Again, we assume that the distinct points C1,..., C are contained [0, 1]. Then, there exists token-wise RELU network g I of width 2 such that for any K E N, >> 0, and all [0, 1] D
g(x) = ạK (a)
where DK.5 and quantization function QK (x) is defined in Appendix F.7. Next, choose the same precision and small enough 8 that satisfies 2 (K++1) < infeyje(k) |c; cyl and < (-(K(2)
We now implement a BRNN cell R: RIxT 1 of width defined follows:
R())[t + 1] = R2LU(2-K x R(x)[t| + #
- R())[t - = RELU(2 x R())(t] + +2 KT xlt 11),
R())[4 R(())( + [z)][
Then, R successfully accumulates (d, bits for z|1 t and (d, (T -T 1))- for ælt T]-
Note that 2- KT x-KTxtt 1] in R enables us to prevent overlapping of information from R by storing data bits in different positions.
Lastly, let G RIXT
R IXT be a RELU BRNN of width 2 such that G(x) =
(o(=[1)),... ... (((()) for all RT Then, the RELU BRNN f Ro G of width 2 completes the proof of Lemma 30.
34


Reviews:
[{"review_id": "jqElg5Vu2T", "reviewer": "Reviewer_4yPi", "summary": "In this paper, the authors study the universal approximation problem of deep neural networks with unlimited depth. The main contribution of this paper is to derive that when the input domain and output domain are $[0,1]^{d_x}$ and $\\mathbb R^{d_y}$ respectively, the minimum width of the universal approximation of neural networks for $L^p$ functions is equal to $\\max(d_x,d_y,2)$, when the activation function is similar to RELU (e.g., RELU, GELU, SOFTPLUS). The authors also show that if the activation function is a continuous function that can be uniformly approximated by a sequence of continuous one-to-one functions, then the minimum width of the universal approximation of neural networks for continuous functions is at least $d_y+1$ if $d_x<d_y \\leq 2d_x$.", "questions": "As explained above, It would be more interesting if the authors could study the exact minimum width for more architectures used in practice.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: The related works are adequately cited. The main results in this paper will certainly help us have a better understanding of the universal approximation property of deep neural networks from a theoretical way. I have checked the technique parts and found that the proofs are solid. One of the main results, which shows that there is a dichotomy between $L^p$ and uniform approximations for general activation functions and input/output dimensions, is a non-trivial extension of previous results in this field.\n\nQuality: This paper is technically sound.\n\nClarity: This paper is clearly written and well organized. I find it easy to follow.\n\nSignificance: I think the results in this paper are not very significant, as explained below.", "weaknesses": "However, I have several concerns about the contribution of this paper. Firstly, the paper (Cai, 2023) already proved that the minimum width of the universal approximation of neural networks for $L^p$ functions is equal to $\\max(d_x,d_y,2)$, when the activation function is Leaky-RELU. This paper only generalizes Leaky-RELU to RELU-LIKE activations (e.g., RELU, GELU, SOFTPLUS), and derives the same result. I think this makes the contribution of this paper incremental. Also, It would be more interesting if the authors could study the exact minimum width for more architectures used in practice. Furthermore, the technical part is not very deep and mostly based on the technical results from previous papers such as (Cai, 2023). In summary, I think this paper is a decent paper with some good results, but may not be suitable for the top conferences such as ICLR.", "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": "", "extra_scores": {}}, {"review_id": "Tjaya5FjCG", "reviewer": "Reviewer_fZsP", "summary": "The authors, in a sense, improve on the available results quantifying the minimal widths required for a class of deep but narrow MLPs to be universal in $C([0,1]^{d_X},\\mathbb{R}^{d_Y})$.    The result is very interesting, and of a technical nature; namely, they show that minimal width can (but surprisingly and not shockingly) be improved when only considering approximation of functions on the cube and not the entire domain $\\mathbb{R}^{d_X}$.", "questions": "** 1) Impact of metric entropy on minimal width?**\n\nFix a compact subset $X$ of $\\mathbb{R}^{d_X}$, non-empty.  Suppose that we are looking for universal approximators in $C(X,\\mathbb{R}^{d_Y})$  implementable by MLPs with ReLU-Like activation function and of bounded widths.  How do you expect that the metric entropy/capacity of $X$ will impact the minimum width?\n\n\nFor instance, if $X=\\{x_0\\}$ is a singleton and $d_Y=1$, then clearly the width $\\min\\{d_X,d_Y,2\\}$ is suboptimal since the class since the class\n$$\n\\{ x\\mapsto a\\operatorname{ReLU}(1\\cdot (x+b)):\\, a\\in \\mathbb{R} ,\\, b:= -x_0 + 1\\}\n$$\nis universal in $C(X,\\mathbb{R})$.  So I guess there is room for improvement for general $X$.  (The same question applies to the case where $d_X=0$ and $d_Y=1$, in which case the minimum width is\n$$\n1 < \\max\\{d_X,d_Y,2\\}=\\max\\{0,1,2\\}=2.\n$$\n\n\n----\n\nWhat's your intuition on how the metric entropy of $X$ appears into the estimate?  \n\n\nI thought about the case where $X=\\{-1,1\\}$ but minimal width seems to apply there also.  What am I missing?\n\n\n\n----\n\n** 2) Why not note more general implications?**\n\nPerhaps I missed it, but it could be worth noting that your results also imply the minimal widths for universality/density in $C(\\mathbb{R}^{d_X},\\mathbb{R}^{d_Y})$ in the topology of uniform convergence on compact sets.  This is because of the extension and normalization arguments as in the proof of Proposition 3.10 [1] or in the proof of Proposition 53 [2], which allows one reduce the problem of universality in $C([0,1]^{d_X},\\mathbb{R}^{d_Y})$.  I.e. using either of the Tiezte or McShane extension theorems\n\n\n** 3) Improving Minimal Width Estimates for general nonlinearities**\n\nIn [5], the authors just recently showed that most MLPs with standard and continuous activation functions can approximately implement and MLP with ReLU activation function using roughly the same depth, width, and number of parameters.  I was wondering, unless I am missing something, why not use their results to sharpen your statement for general continuous activation functions?\n\n- References -\n\n[1] Acciaio, Beatrice, Anastasis Kratsios, and Gudmund Pammer. \"Designing universal causal deep learning models: The geometric (Hyper) transformer.\" Mathematical Finance (2023).\n\n[2] Kratsios, Anastasis, and Léonie Papon. \"Universal approximation theorems for differentiable geometric deep learning.\" The Journal of Machine Learning Research 23, no. 1 (2022): 8896-8968.\n\n[3] Arenas, Francisco García, and María Luz Puertas. \"Tietze's extension theorem.\" Divulgaciones Matemáticas 10, no. 1 (2002): 63-78.\n\n[4] Beer, Gerald. \"McShane’s extension theorem revisited.\" Vietnam Journal of Mathematics 48, no. 2 (2020): 237-246.\n\n[5] Zhang, Shijun, Jianfeng Lu, and Hongkai Zhao. \"Deep Network Approximation: Beyond ReLU to Diverse Activation Functions.\" arXiv preprint arXiv:2307.06555 (2023).", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The results are interesting, especially for those studying the fundamental limits of MLPs and their approximation theory. The presentation is clear and the proofs are mathematically correct.  \n\nThough one may foreseeable argue that the contribution is of a technical nature, these results answer fundamental questions at the core of the validity of practical MLP implementations. \n\nIn short, I think these results should definitely be published :)", "weaknesses": "The paper is rigorous and I do not see any weaknesses; with one exception:\n\n- Can the authors please add more details and rigor in the construction in Lemma 6's proof.  I know a lot of it is drawn from another paper's lemmata but it would be better to have it explicit and self contained.  Right now it is not even a proof but a proof sketch/recipe.", "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": "", "extra_scores": {}}, {"review_id": "QKHXkw7MiL", "reviewer": "Reviewer_FUZf", "summary": "This work studies the minimum width required for universal approximation ability of neural networks, under general settings with varying norm, input/output dimensions and activation functions. In particular, this work generalizes the result of Cai 2023, showing that the minimum width is exactly $\\max(d_x,d_y,2)$ for neural networks with ReLU-class activations to approximate $L^p$ functions from a compact set of $\\mathbb{R}^{d_x}$ to $\\mathbb{R}^{d_y}$. Then it's shown that when uniform approximation is considered, the minimum width is at least $d_y+1$ when $d_x\\le d_y\\le 2d_x$, implying a dichotomy between $L^p$ and uniform approximation.", "questions": "As a side note, the separation between the whole Euclidean space and compact subset (equivalently, $L^p$ versus uniform) was noticed even before Wang and Qu 2022. In a technical report of Lu [1], it's shown that any two-layer ReLU network must incur $\\int_{\\mathbb{R}^d}|f|$ error to approximate an integrable function $f$, a sharp contrast to the case when the integral is deployed on a compact set. Their argument is very simple and may be potentially helpful for explaining the intuition of such separation results.\n\n[1], A note on the representation power of ghhs, Zhou Lu, arXiv preprint 2101.11286", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Solid results:** the theoretical results make a solid contribution to the understanding of the universal approximation ability of neural networks.\n\n**Wide coverage:** Theorem 2 holds for a wide class of ReLU-like activations, while previous works mostly consider only the most representative ReLU. Though such result is well expected due to the similarity between these activations, and indeed the proof is based on a simple reduction, it is non-trivial and such generality is valuable.\n\n**Tight bounds:** since the initial work of Lu et al 2017 which achieves the $d_x+4$ bound in the particular setting with $L_1$ norm, $d_y=1$ and ReLU activation, there has been a line of works on sharpening the bound itself, and generalizing the setting to other norms and activations. This work finally presents an exact characterization of the minimum width for general $L^p$ norm and a wide class of ReLU-like activations.", "weaknesses": "**Questionable significance:** though this work makes a solid contribution to a tight characterization of the minimum width for universal approximation which is certainly valuable for our theoretical understanding, in my opinion, the mission itself to improve upon previous results is not so significant. The gap between known upper and lower bounds is merely an additive constant, and a similar tight result was achieved in Cai 2023 for the special case of Leaky-ReLU.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)