Achieve the Minimum Width of Neural Networks for Universal Approximation
Authors: Yongqiang Cai
Venue: ICLR 2023 poster (2023)
Keywords: Universal Approximation
Feedforward Neural Network
Leaky-ReLU

Abstract: The universal approximation property (UAP) of neural networks is fundamental for deep learning, and it is well known that wide neural networks are universal approximators of continuous functions within both the $L^p$ norm and the continuous/uniform norm. However, the exact minimum width, $w_{\min}$, for the UAP has not been studied thoroughly. Recently, using a decoder-memorizer-encoder scheme, \citet{Park2021Minimum} found that $w_{\min} = \max(d_x+1,d_y)$ for both the $L^p$-UAP of ReLU networks and the $C$-UAP of ReLU+STEP networks, where $d_x,d_y$ are the input and output dimensions, respectively. In this paper, we consider neural networks with an arbitrary set of activation functions. We prove that both $C$-UAP and $L^p$-UAP for functions on compact domains share a universal lower bound of the minimal width; that is, $w^*_{\min} = \max(d_x,d_y)$. In particular, the critical width, $w^*_{\min}$, for $L^p$-UAP can be achieved by leaky-ReLU networks, provided that the input or output dimension is larger than one. Our construction is based on the approximation power of neural ordinary differential equations and the ability to approximate flow maps by neural networks. The nonmonotone or discontinuous activation functions case and the one-dimensional case are also discussed.

Published as a conference paper at ICLR 2023
ACHIEVE THE MINIMUM WIDTH OF NEURAL NET- WORKS FOR UNIVERSAL APPROXIMATION
Yongqiang Cai* Beijing Normal University selyq.math@tee edu.
ABSTRACT
The universal approximation property (UAP) of neural networks is funda- mental for deep learning, and it is well known that wide neural networks are universal approximators of continuous functions within both the LP norm and the contimuous/ /uniform norm. However, the exact minimum width, Wmin+ for the UAP has not been studied thoroughly. Recently, us- ing decoder-memmoizzaeennodd
scheme, Park et al. (2021) found that Wmmin = max(d, + 1, 1,d,) for both the IP-UAP of ReLU networks and the C-UAP of ReLU+STEP networks, where dz, are the input and out- put dimensions, respectively. In this paper, we consider neural networks with an arbitrary set of activation functions. We prove that both C-UAP and LPPUAP for functions on compact domains share a universal lower bound of the minimal width; that is, Wmip max(dz.d. dy). In particular, the critical width, wine for L--UAP can be achieved by leaky-ReT.U net- works, provided that the input output dimension is larger than one. Our construction is based on the approximation power of neural ordinary differential equations and the ability to approximate flow maps by neural networks. The nonmonotone or discontinuous activation functions case and the one-dimensional case are also discussed.
1 INTRODUCTION
The study of the universal approximation property (UAP) of neural networks is fundamental for deep learning and has long history. Early studies, such as Cybenkot (1989): Hornik
eel al. (1989); Leshno et. al. (1993), proved that wide neural networks (even shallow ones) are universal approximators for continuous functions within both the T norm (1 S p < oe) and the continuous/ continuous/uniform uniform norm. Further research, such as Telgarsky (0166). indicated that
increasing the depth can improve the expression power neural networks. If the budget number of the neuron is fixed, the deeper neural networks have better expression power Yarotsky Zhevnerchuk (2020); [hhn al. (2022). However, this pattern does not hold if the width is below a critical threshold Wmin- Lu et al. (2017) first showed that the ReLU networks have the UAP for L functions from Rd to the width larger than dg + 4, and the UAP disappears if the width is less than d.. Further research, Hanin & Sellke) (2017); Kidger & Lyons) (2020); Park el al.] (202T). improved the minimum width bound for ReLU networks. Particularly, Park et al. (2021) revealed that the minimum width is Wmin = max(d, + I, d,y) for the LP(I"", FF) UAP of ReLU networks and for the C(C, Rd) UAP of RcLU+STEP networks, where IC is a compact domain in Rd.
For general activation functions, the exact minimum width Wmin for UAP is less studied. Johnson (2019) consider uniformly continuous activation functions that can be approximated by a sequence of one-to-one functions and give lower bound Wmin 2 d, for C-UAP (means UAP for C(C., TRdd.) ))- Kidger & Lyons (2020) consider continuous nonpolynomial activation functions and give upper bound Wiin dz dy + 1 for C-UAP. Park al.
2021 improved the bound for LP-UAP (means UAP for L IE,C to Wmin max(d, +
'School of Mathematical Sciences, Laboratory of Mathematics and Complex Systems, MOF, Beijing Normal University, 100875 Beijing, China

---

Published as a conference paper at ICLR 2023
d, + 1). A summary of known upper/lower bounds minimum width for the UAP can be found in Park et al. (222)).
In this paper, consider neural networks having the UAP with arbitrary activation fune- tions. We give a universal lower bound, Wmin 2 wiin = max(dz, dy), to approximate functions from a compact domain C I to Rd in the L norm or continuous norm. Fur- thermore, we show that the critical width "iin can be achieved by many neural networks, as listed in Table [ Surprisingly, the leaky-ReLU networks achieve the critical width for the L--UAP provided that the input. output dimension is larger than one. This result relies on a novel construction scheme proposed in this paper based on the approximation power of neural ordinary differential equations (ODEs) and the ability to approximate flow maps by neural networks.
Table 1: Summary of the known minimun width of feed-forward neural networks that have the universal approximation property.
Functions
Activation
Minimum width
References
C(K, IR)
ReLU
Wmin +1
Hanin & Sellke (2017)
LP(R6, R24)
ReLU
Wmin max(d, 1, 1,dy)
Park el. al.
202
C((0, 1).T) 1R2)
ReLU
Wmin = 3 max (dz, dy) +1
Park et. al.
2021
C(K, IR.))
ReLU+STEP
Wmin max(d, 1, 1,dy)
Park et al.
2021
LP(K, R2)
Conti. nonpoly
Wmin max(dd 2, dy + +
Park et al.
(2021)
LP LP(K, Rd)
Arbitrary
Wmin max(dd,, dly)
Wmin
Ours [Lemmaa
Leaky-ReL.U
Wmin max(d,, dy. 2)
Ours Theorem
Leaky-ReLU+ABS
Wmin max(de. dry)
Ours Theorem
C(C,
Arbitrary
Wmin max(d,, (d,,, dly)) =: w Wiinn
Ours
Lemma
ReLU+FLOOR
Wmin max do, dy. 2)
Ours (Lemma
UFL
W Wmin = max(d dy)
Ours Corollarr
C(10, 144
UOE
Wmin dy
Ours (Theorem
I Continuous nonpolynomial that continuously differentiable at some with (2) + 0.
i UOE means the function having universal ordering of eztrema, see Definition
1.1 CONTRIBUTIONS
1) Obtained the universal lower bound of width wiin for feed-forward neural networks (FNNs) that have universal approximation properties.
2) Achieved the critical width whin by leaky-ReLUU+ABS networks and UOE+ networks. (UOE a contimuou function which has universal ordering of extrema. It introduced to handle C-UAP for one-dimensional functions. See Definition 7
3) Proposod a novel construction scheme from a differential geometry perspective that could deepen our understanding of UAP through topology theory.
1.2 RELATED WORK
To obtain the exact minimum width, one must verify the lower and upper bounds. Generally, the upper bounds are obtained by construction, while the lower bounds are obtained by counterexanples.
Lower bounds. For ReLU networks, Lu et al. (2077) utilized the disadvantage brought by the insufficient size of the dimensions and proved lower bound Wmin 2 dz for I UAP; Hanin & Sellke (2017) considered the compactness of the level set and proved a lower bound Wmin 2 d,, +1 +I+ffo for C-UAP. For monotone activation functions its variants, Johnsonl (2019) noticed that functions represented by networks with width de have unbounded level compact domain IC take their maximum value on the boundary Oc. These properties allow one to construct counterexamples and give lower bound Wmin 2 d, for C-UAP. For general activation
sets, and [Beise & Da Cruz (2020) noticed that such functions
2

---

Published as a conference paper at ICLR 2023
functions, Park et al. (2021) used the volume of simplex in the output space and gave lower bound Wmin 2 dy for either LP-UAP or C-UAP. Our universal lower bound, wmin 2 max(dy, dy), is based on the insufficient size of the dimensions for both the imput and output space, which combines the ideas from these references above.
Upper bounds. For ReLU networks, Lu et al. (2017) explicitly constructed width-(d, +4) network by concatcnating a series of blocks so that the whole network can be approximated
by scale functions in ( IR) to any given accuracy. Hanin & Sellke (2017); Hanin (0119) constructed a width-(d, + dy) network using the max-min string approach to achieve C- UAP for functions on compact domains; Park et al.) (2021) proposed an encoder-memorizer- decoder scheme that achieves the optimal bounds Wmin max de + 1, dy) of the UAP for
For general activation functions, Kidger & Lyons (2020) proposed a register for C-UAP. Basod on this result. Park et al. (2021) improved the upper bound to Wmin I max(d, + 2, dy + for LP-UAP. this paper, we adopt the encoddrr-eenorriee--eeeedd universal critical width for C-UAP by ReLU+FLOOR activation functions. However, the floor function is discontimuous. For LP-UAP, we reach the critical width by leaky-ReLLU which is a contimuous network using novel scheme based on the approximation power of neural ODEs.
model construction that gives an upper bound Winin S dz + dy
scheme to calculate the
ResNet and neural ODEs. Although our original aim is the UAP for feed- forward neural networks, our construction is related to the neural ODEs and residual networks (ResNct, He ct al. (2016)). which include skipping connections. Many studies, such as E (2017 [: Lu et al. (2018); Chen el al. (2018). have emphasized that ResNet can be regarded as the Euler dis- cretization of neural ODEs. The approximation power of ResNet and neural ODEs have also been examined by researchers. To list a few, Li et al. (2022) gave a sufficient condition that covers most networks in practice so that the neural ODE dDE/dynamic systems (without extra dimensions) process LP-UAP for continuous functions, provided that the spatial dimension larger than one: BRuiz-Balet & Zuazua (2021) obtained similar results focused on the case of one-hidden layer fields. "Tabuada & Charcsifard (2020) obtained the C-UAP for mono- tone functions, and for continuous lunctions it was obtained by adding one extra spatial dimension. Recently, Duan et al. (2022) noticed that the FNN could also be discretization of neural ODEs, which motivates us to construct networks achieving the critical width by inheriting the approximation power of neural ODEs. For the excluded dimension one, design an approximation scheme with leaky-ReT.U+AND and UOE activation functions.
1.3 ORGANIZATION
We formally state the main results and necessary notations in Section The proof ideas
are given in Section 3 4 and 5 In Section 3 we consider the case where N = dg = dy
which is basic for the high-dimensional cases. The construction is based on the properties
of monotone functions. In Section 4 we prove the case where N = dN dy 2 2. The construction is based on the approximation power of neural ODEs. In Section 5 we consider the case where d₂ F dy and discuss the case of more general activation functions. Finally, we conclude the paper in Scction D Appendix.
All formal proofs of the results are presented in the
2
MAIN RESULTS
In this paper, we consider the standard food-forward neural network with N neurons at each hidden layer. We say that a network with depth L function with inputs æ E Rd, and outputs y E Rdy, which has the following form:
y == fx) = W C.VVV-..-WWi... (Wix b1) )...) + bz) but1,
(1)
where b; are bias vectors, W; are weight matrices, and a(.) is the activation function. For the case of multiple activation functions, for instance, d1 and d2, we call fo a 01t02 network. In this situation, the activation function of each neuron is either 01 or 02. In this paper, we consider arbitrary activation functions, while the following activation functions are emphasized: ReLU (max(æ, 0)), leaky-Rel.U (max(x, (0, 1) is fixed positive
3

---

Published as a conference paper at ICLR 2023
parameter), ABS (|z)), SIN (sin(z)), STEP (12s0), FLOOR ([x1) and UOE (universal ordering of extrema, which will be defined later).
Lemma 1. For any compact domain K Rd, and any finite set of activation functions { the {os} networks with width w < Wiin max(dz, dy) do not have the UAP for both LPCC,12) and C(K,RA,
TP-UAP and C-UAP. The lemma indicates that w bound for the UAP in both I"(K, R4) and C(C, R.). The main result of this paper illustrates that the minimal width Wmin can be achieved. We consider the UAP for these two function classes, i.e., LP-UAP and C-UAP, respectively. Note that any compact domain can be covered by big cubic, the functions the former can be extended to the latter, and the cubic can be mapped to the unit cubic by a linear function. This allows us to assume K. to be (unit) cubic without loss of generality.
min = max(d,, dy) a universal lower
2.1 LP-UAP
Theorem 2. Let IC C Rdd be a compact set; then, for the function class (P(C,RA)) the minimumn width of leaky-ReLU nelworks having LP- TP-UAP eraclly Wiin max(dd, dyy 2).
The theorem indicates that Beaky-ReLU networks achieve the critical width w max d2., dy). except for the case of d, d, d, = dy d > 1 and let the network width equal d. According to the results of Duan et al. (2022), leaky-ReI.U networks can approximate the flow map of neural ODEs. Thus, we can use the approximation power of neural ODEs to finish the proof. Li et al. 2022 proved that many neural ODEs could approximate continuous functions in the L norm This is based on the fact that orientation preserving diffcomorphisms can approximate continuous functions Brenier & Gangbo (2003).
The idea is to consider the case where
The exclusion of dimension one is because of the monotonicity of leaky ReLU. When add a nonmonotone activation function such as the absolute value function or sine function, the TPP at dimension one be achieved.
Theorem 3. Let C. Rd= be compact set; then, for the function class L*(,, the min- Smum width of leaky- ReL U ABS networks having TP- -UA is exactly wmin = max (dz, dy).
2.2 C-UAP
C-UAP is more demanding than LP-UAP. However, if the activation functions could in- clude discontinuous functions, the same critical width wiin can be achieved. Following the encodder-memory--eeeodeee approach in Park et al. (2021), , the step function is replaced by the floor function, and one can obtain the minimal width Wmin = max (dz 2, dy).
Lemma 4. Let K. C Rd be compact set; then, for the function class C(K,, Rdv), , the min- émum width of ReLU+FLOOR networks having C-UAP is eractly Wmin max(da: 2, dy).
Since ReLU and FLOOR are monotone functions, the C-UAP critical width whin does not hold for C(JO, 1], R). This soems to be the case even if we add ABS or SIN as an additional activator. However, it is still possible to use the UOE function (Definition 12
Thcorem 5. The UOE networks with width dy have C-UAP for functions in C((0, 1), R.)..
Corollary 6. Let K. C Rd, be compact set; then, for the continuous function class C(K,R Rd2,, the minimum width of UOE+FLOOR networks having C-UAP is exactly Wmin = max(d dy).
3 APPROXIMATION IN DIMENSION ONE (N = d, = ddy = 1
In this section, we consider one-dimensional functions and neural networks with a width of one. In this case, the expression of ReLU networks is extremely poor. Therefore, consider the leaky ReLU activation (2) with a fixed parameter a E (0, 1). Note that leaky-ReLL is strictly monotonic, and it was proven by Duan et al. (2022) that any monotone function in
4

---

Published as a conference paper at ICLR 2023
C( 1|. R) can be uniformly approximated by leaky-ReLU networks with width one. This useful for our construction to approximate nonmonotone functions. Since the composition of monotone functions is also monotone function, to approximate nonmonotone functions we need to add a nonmonotone activation function.
Let consider simple nonmonotone functions, such as |x] sin(2). We show that leaky- ReLU+ABS or +eaKy-ReLU++IIN can approximate any continuous function (*) under the L norm. The idea, shown in Figure [ is that the target function f (ax can be uniformly approximated by the polynomial p(z), which can be represented as the composition
g o u(x( = p(x) (x).
Here, the outer function g(z) is any continuous function whose value at extrema matches the value extrema of p(r), and the inner function u(z) monotonically increasing, which adjusts the location of the extrema (sce Figure D. Since polynomials have finite number of extrema, the inner function u(x) is piecewise continuous.
(b)
1100
+D2 H622
24
MDU) 9002 +00
Figure 1: Exammpe of approximatting/eepresentte monotonically increasing function u(x) and a nonmonotone function g(x). (a) only matching the ordering of extrema values, (b) matching the values as well.
polynomial by the composition of
For LP-UAP, the approximation is allowed have a large deviation on a small interval: therefore, the extrema could not be matched exactly (over small error). For example, we can choose g(x) as the sine function or the sawlooth function (which can be approximated by ABS networks), and u(x) is leaky-ReI.U network approximating g -1 o p(x) at each monotone interval of p. Figure (a) shows an example of the composition.
For C-UAP, matching the extrema while keeping the error small is needed. To achieve this aim, we introduce the UOE functions.
Definition 7 (Universal ordering of extrema (UOE) functions). A UOE function is con- tinaous function in C(R, R) such that any (finite number of) possible ordering(s) of values at the (finite) extrema can be found in the extrema of the function.
There infinite number of UOE functions. Here, we give example, shown in Figure This UOE function p(x) is defined by a sequence {o
x/
I < 0,
plx)=
(2)
o + (I-
x x (i+++),,
4,... the con- catenation of all permutations of positive integer mumbers. The term UOE in this paper means this function p. Since the UOE function p(x) can represent leaky-ReLU 01/4 on any finite interval, this implies that the UOE networks can uniformly approximate any monotone functions.
where {0:],0 11221122212222133333332222222221
1,2,3 1,
To illustrate the C-UAP of UOE networks, only need to construct continuous function g(x)) matching the extrema of p(z) (see Figure [()). That is, construct g(z) by the com- position u o p(x), where ū(x) is monotone and continuous function. This is possible since the UOE function contains any ordering the extrema.
The following lemma summarizes the approximation of one-dimensional functions. As consequence, Theorem 5 holds since functions in C(O0, 1], R4, can be regarded as d, one- dimensional functions.
5

---

Published as a conference paper at ICLR 2023
Figure 2: An example of the UOE function p(x), which has an infinite number of pieces.
Lemma 8. For any function (*) E CiO, and O, there a leaky-ReLUU-ADE (or
leaky-Ree..S R network with width one and depth I, such that fn (z()) xaax<sa eP There a leaky-ReLLU ReLU+ UOE network with width of one and depth of such that (z) 1 fr(x)) <,, Vx [0,
4 CONNECTION TO THE NEURAL ODES (N = =
Now, we turn to the high-dimensional case and connect the feod-forward neural networks to neural ODEs. To build this conncction, assume that the input and output have the same dimension, dN ===, dy = d.
Consider the following neural ODE with one-hidden layer neural fields:
(t) v(<(t),t) == A(t) (anh(W(t)z(()) + b(t)), (0, xx( To.
(3)
where x, zo, E Rd and the time-dependent parameters (A, W) Rdxd Rdxd x R are piccewise constant functions of t. The flow map is denoted as (-((), which is the function from To to x(r). According to the approximation results of neural ODEs (sce Li et al. (2022) Tabuada & Gharesifard 2020); Ruiz- Balet. & Zuazua 2021 for examples), we have
the lollowing lemma.
Lemma 9 (Special case of Li ct al.
(002 ). Let d 2 2. Then, for any continuous function R. and any ε > O, there erist lime T E RR and [ + Raxd x Badd x Rd so that the flow-map or
I" RRd + Rd, any compact set
pieceuise constand inpul (A, W. b)
associated with the neural ODE satisfies: Ilf - - (1 S.
Next, we consider the approximation the flow map associated with (3 by neural net- works. Recently, Duan et al. (2022) found that leaky-ReLU networks could perform such approximations.
Lemma 10 (Theorem 2.2 in Duan et al. (2022)). If the parameters (,, in 3 are piecewise constants, then for any compact set K. and any e > O, there is a network fI( with width d and depth L such that
l1 (x) fz(2)) S SE,AE V.
(4)
Combining these two lemmas, of our Theorem 2
directly prove the following corollary, which is part
Corollary 11. Let C RRd compact set and 2 2; then, for the function class LP(K, the Baky-RRLLU networks with width d have LP-UAP
Here, we summarize the main ideas of this result. Let us start with the discretization of the ODE by the splitting approach (see McLachlan & Quispel (2002) for example). Consider the spliting of (3) with v(z, l) = E., 0. u (z, f)eG, where w. (5) (x. = A)a(1) tanh(W...(()az + bx())) a scalar function and ej is the jith axis unit vector. Then for given time step At T/K, (K large enough), the splitting method gives the following iteration of I& which approximates (*S(())))
Tk+1 (ddaa) o... T (1.2 T(O (1.1) Ik.
(5)

---

Published as a conference paper at ICLR 2023
where the map Th ((dd)) x y is defined as
y ( x²) 11
(6)
y() - + (x, (A,) z00) aAl tanh(wx -3)-
Here the superscript in 209) means the 1-th coordinate of z. AJi, w W.: and b lake their value al t= KAL Note that the scalar functions (anh(g) and & + a&d tanh({) are monolone with respect to & when Al is small enough. This allows us to construct leaky- ReLU networks with width d to approximate each map (K.) and then approximate the flow-map, 6² (mr) KK.
Note that Lemma 10 holds for all dimensions, while Lemma g holds for dimensions larger than one. This is because flow maps are orientation- prrerioin-peeeviinggg diffeomorphisms, and they can approximate continuous functions only for dimensions larger than one; see Brenier & Gangbo (2003). The approximation is based on control theory where the flow map can be adjusted to match any finite set of input-output pairs. This match does not hold for dimension one. However, the case dimension one is discussed in the last section.
ACHIEVING THE MINIMAL WIDTH
Now, turn to the cases where the input and output dimensions cannot be equal.
5.1 UNIVERSAL LOWER BOUND whin max(da, dy)
Here, we give a sketch of the proof of Lemma 1 which states that "i is a universal lower bound over all activation functions. Parts of Lemma [ have been demonstrated in many papers, such as Park et al. (2021). Here, we give proof by two counterexamples that are simple and easy understand from the topological perspective. It contains two cases: 1) there is a function f" that cannot be approximated by networks with width w S d2 1; 2) there is a function f* that cannot be approximated by networks with width w S dy 1. Figure B(a)-bb shows the counterexamples that illustrate the essence of the proof.
For the first case, w S d 11 1, we show that (x) ||x|| x E K [-2, is what we
want; see Figure 3(a) In fact, we can relax the networks to a function f(x) = o(Wx + b), where Wx + is a transformer from Rdd Rd.-1 and Φ(xx could be any function. A
consequence is that there exists direction (set the vector satisfying We = 0, ||||| = =1
such that f(x) = f(x + Au) for all X E R. Then, considering the sets A {ar |||||| S 0.13 and B = fo | all 0.13. we have
[ [f(z) - ( V / 1f(z) - (f)))- + [f(x) (x))
[ (15(x) (-)) 150++++(x+000 fr + v)))dr
/ - - 2 0.8|A).
Since the volume of A a fixed positive number, the inequality implies that even the L approximation for f is impossible. The case of the Lt norm and the uniform norm is impossible as well.
For the second case,
11, show the example of f*, which is the parametrized curve from 0 to 1 along the edge of the cubic, see Figure 3tg Relaxing the networks to a function f(x Wx((>) + b, vb(x)) could be any function. Since the range of in a hyperplane while f has a positive distance to any hyperplane, the target f cannot be approximated.
5.2 ACHIEVING Wi FOR LP-UAP
Now, we show that the lower bound wiin for LP-UAP can be achieved by leaky-ReLU+ABBS networks. Without loss of generality, we consider K. [0, 1]4..
7

---

Published as a conference paper at ICLR 2023
For any function f in L"( Rdv), we extend it to function f in L 1]4, R*) by filling in zeros where d = max(dz, d,) W When de > 1 or dy > the LP-UAP for leaky-ReLU networks with width min is obtained by using Corollary the Temma I
Recall that by
wiin is optimal, and we obtain our main result Theorem
Combining the case of d, dy d = 1 in Section 3 adding absolute function ABS additional activation function, we obtain Theorem
5.3 ACHIEVING Wiin FOR C-UAP
Here, we use the mooder-memorizz--dee approach proposed Park al. (2021) to achieve the minimum width. Without loss of generality, consider the function class C(OO, 1j [0, 1jdv). The picoder-meooizzer-deedeee approach includes three parts:
1) an encoder maps [0. 1] [0, which quantizes each coordinate of by a K- bit binary representation and concatenates the quantized coordinates into single scalar value having (d, J-bit binary representation;
2) a memorizer maps each codeword its target codeword y;
3) a decoder maps y to the quantized target that approximates the true target.
As illustrated in Figure c), using the floor function instead of step function, one can construct the encoder by FLOOR networks with width dz and the decoder by FL.OR networks with width dy The memorizer is a one-dimensional scalar function that be approximated by ReLU networks with width of two or UOE networks with a width of one. Therefore, the minimal widths max(d2, 2, dy) and max(day dy) are obtained, which demonstrate Lemma 4 and Corollary respectively.
(b)
19
quantization
concstenate
encoder
P50 EalE
00.1011
0.10111
(2-1.2-1 2-22--2--- [2xx]
0.1100
0.1100
memorizer
0.0101/
y
0.001011010111000
/0.00101
0.10110
0.00101
0.10110
2
2
0
7
[25y]
decoder
0.11001
0..11001
25
-1
2
(2
(a)(b) Counterexamples for proving Lemma (a) Points A and B on a level set of networks (x);; ((A) [(B) but (A) (B) is not small. (b) The curve from to 1 along the edge of the cubic has positive distance to any hyperplane. (c) illustration of the poooolee-mmmorzee--eeeeeeo
Figure 3:
scheme for C-UAP by an example where dg dy = 3,
bits for the input and 5 bits for the output.
5.4 EFFECT OF THE ACTIVATION FUNCTIONS
Here, we emphasize that our universal bound of the minimal width is optimized over ar- bitrary activation functions. However, it cannot always be achieved when the activation functions are fixed. Here, we discuss the case of monotone activation functions.
If the activation functions are strictly monotone and continuous (such as leaky-ReLU), width of at. least. d, + 1 is needed for C-UAP. This can be understood through topology theory. Leaky-ReLU, the nonsingular linear transformer, and its inverse are continuous and homeomorphic. Since compositions of homeomorphisms have the following proposition: If N = d, = d, = d and the weight matrix in leaky-ReLU networks nonsingular, then the input-output map is honcomorphism. Note that singular matrices can be approximated by nonsingular matrices; thorefore, we can restrict the weight matrix in neural networks to the nonsingular case.
also homeomorphisms,
When d, 2 dy. we can reformulate the leaky- ReLU network as fi(2) = Wr+10(()) + b where (x) is the homeomorphism. Note that considering the where d, =1 is sufficient,
8

---

Published as a conference paper at ICLR 2023
They proved that the neural network width dg cannot approximate any scalar function with a level set containing a bounded path component. This be easily understood from the perspective of topology theory. An example to consider the function (x) = |,l|, x E K. = [-2, 2) shown in Figure
according to Hanin & Sellke [2017] Johnson 2019
(
y
(8)
Inner point
Impossible for hontemmorphssss
Boundar F- (8.)
Bounday
point
(a) Plot of fTx ||=|| and its contour at ||a||| = 1. (b) The original point P is an inner point of the unit ball, while its image boundary point, which impossible for homeomorphisms. (c) Any homeomorphism, approximating | with error less than & (=0.1 for example) on I', should have error larger than 1 - (-0.9) at P. (d) Approximating f in L is possible by leaving a small region.
Figure 4: Mustrating the possibility of UAP when N d
The case where de dy. We present simple example in Figure 5 The curve '4' corre- sponding to continuous function from [0, 1] C R to R2² cannot be uniformly approximated. However, the I approximation is still possible.
(a)
(b)
Possible (uniffom UAP)
Impossible
Possible (IP UAP)
(uniform UAP)
Figure 5: Mustrating the possibility of C-UAP when d, S dy. The curve in (a) is homeo- morphic to the interval [0, 1], while the curve '4' in (b) is not and cannot be approximated uniformly by homeomorphisms. The L approximation is possible via (a).
CONCLUSION
Let summarize the main results and implications of this paper. After giving the universal lower bound of the minimum width for the UAP, we proved that the bound is optimal by constructing neural networks with some activation functions.
For the LP-UAP, our construction to achieve the critical width was based on the approxi- mation power of neural ODEs, which bridges the food-forward networks to the flow maps corresponding to the ODEs. This allowed us to understand the UAP of the FNN through topology theory. Moreover, we obtained not only the lower bound but also the upper bound.
approach For the C-UAP, our construction was based on the discontinuous function [x]. Tt is in Park al. (2021), where the activation sets contain
still open question whether we achieve the critical width by continuous activation functions. Johnson 2019) proved that continuous and monotone activation functions need at least width d, This implics that nommonotone activation functions noeded. By using the UOE activation, we calculated the critical width for the case of dg = 1. It would be of interest to study the case of d, 2 in future research.
We remark that our UAP is for functions on a compact domain. Examining the critical width of the UAP for functions unbounded domains is desirable for future research.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank anonymous reviewers for their valuable comments and useful suggestions. This rescarch is supported by the National Natural Science Foundation of China (Grant No. 12201053).
REFERENCES
Pans-Peeer Beise and Steve Dias Da Cruz. Expressiveness neural net works having width equal below the input dimension. arXiv preprint (xxx:2211.04992 2020.
Yann Brenier and Wilfrid Gangbo. IP Approximation of maps by diffeomorphisms. Calculus of Variations and Partial Differential Equations, 16(2):147-164, 2003.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31,
2018.
George Cybenkot. Approximation by superpositions of sigmoidal function. Mathemalics of Control, Signals and Systems, 2(4):303-31 314, 1989.
Yifei Duan, Li'ang Li, Guanghua Ji, and Yongqiang Cai. Vanilla feedforward neural networks as a discretization dynamic systems. arXiv preprint arXiv:2209.1000 2022.
Weinan E. A proposal machine learning via dynamical systems. Communications in Mathematics and Statistics, 1(5):1-11, 2017.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and relu activations. Mathematics, 7(10)9992, 2019.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiw: 110.87 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 770-778, 2016.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359 1989.
Jesse Johnson. Deep, Skinny Neural Networks are not Universal Approximators. In Inter- national Conference Learning Representations, 2019.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference learning theory, pp. 2306-2327, PMLR, 2020.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedfor- ward networks with nonpolynomial activation function approximate any function. Neural Networks, 6(6):861-88) 867, 1993.
Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An approx- imation perspective. Journal of the European Mathemalical Sociely, 2022.
Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural net- works: Bridging deep architectures and numerical differential equations. International Conference Machine Learning, pp. 3276-3285. PMLR, 2018.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. volume 30, 2017.
Robert I. McLachlan and G. Reinout W. Quispel. Splitting methods. Acta Numerica, 11: 341-434, 2002.
10

---

Published as a conference paper at ICLR 2023
Sejun Park, Chulhce Yun, Jacho Lee, and Jinwoo Shin. Minimum Width for Universal Approximation. In International Conference on Learning Representations, 2021.
Domenec Ruiz-Balet and Enrique Zuazua, Neural ode control for classification, approxima- tion and transport. arXiv preprint or Xiv:21104 05278, 2021.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, 2022.
Paulo Tabuada and Bahman Gharesifard. Universal approximation power deep residual neural networks via nonlinear control theory. ar preprint orXw:2007.060007, 2020.
Matus Telgarsky. Benefits of Depth in Neural Networks. In Conference on Learning Theory, pp. 1517-1538 PMLR, 2016.
Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. Advances nearal information processing systems, 33:13005 13015, 2020.
11

---

Published as a conference paper at ICLR 2023
A PROOF OF THE LEMMAS
A.1 PROOF OF LEMMA
We give definition and lemma below that are useful for proving Lemma Definition 12. We say two functions, S1; J2 C(TR, have the same ordering of extrema if they have the following properties:
1) fz(z) has only a finite number of extrema that are (increasing) zi.j. = 1, 2, mi
2) mı m2 =: m and the two sequences,
Si == f( (10.://0..........00.00.am....
and
S = (f2(- fa(22) f2) fe(too)) have the same ortering, i.e.,
S < S1j x S2 S2a1 Vi,j,
S1 = S1, + = S2,1 Vi,j.
Lemma 13. Let fi and fz be continuous functions in C(R. R) that have the same ordering of extvema; then, there are two striclly monolone functions, and u, such that
f = U f2 ou.
Proof. Here, we use the same notation in Definition 12 constructed as follows.
The functions and can be
(1) Construct the outer function that tries to match the function values at the extrema. The only requirement is that
=(_ Vi.
Since S₁ and S2 have the same ordering, is easy to construct such function v that is continuous and strictly increasing, for example, piecewise linear.
(2) Construct the inner function to match the location of the extrema. Denote == uo fe, which satisfies fi(xī,)) = g(22,)) Since fi and are strictly monotone and continuous on the intervals I : (2 and Jj = (z). 12,-1), respectively, we can construct the function u on I,
u(x) - (f())
Combining each piece of u, have strictly increasing and continuous function the whole space R. As a consequence, we have fi = o u to f2 o u.
Lemma 8. For any function (*) C(O, 1] and 0,
1) there is a leaky- Re. (or leaky- U+SUN)))) network with width one and depth L such that fo 15*(x)) (1.(x) < eP.
2) there is leaky-ReLU UOE network width one and depth L such that (f()))ff(()) < e, Vx E [0.
Proof. We mainly provide proof of the second point, while the first point can be proven using the same scheme.
For any function (x) E C((0, 1), IR) and & > 0, we can approximate it by a polynomial pa (x) with order n such that.
(f" (n() & Se/2, Vr E [0,
12

---

Published as a conference paper at ICLR 2023
according to the well-known Weierstrass approximation theorem. Without a loss of general- ity, we can assume that (x( is not the same at all of its extrema. Then, we can represent (z) by the following composition, using Lemma 13 and the property of UOE:
Pn(x) = v o p u(x),
(7)
where p(x) is the UOE function (2 and v(x) and u(x) are monotonically increasing contin- uous functions.
Then, we can approximate (x) by UOE networks. Since v(æ) and u(x) are monotone, there are UOE networks ū(x) and ū(z) such that V|v- öll and ||u üll are arbitrarily small.
Hence, there is a UOE network fz(x) = 8 po ū(x) that can approximate pa( such that
(a(()) - [ e/2, Vo E [0,
S
which implies that
- f(()) Se.
This completes the proof of the second point.
For the first point, we only emphasize that it is easy to construct a function f(z) that has the same local maximuum and local minimum in the interval and has |l f Le small enough. This f(z) has the same ordering of extrema as the sawtooth function (or sine) and hence can be uniformly approximated by RelkyRReU++ABS (or leaky-ReLUS ReUU--INN networks fL. As a consequence, ||/r - [ is small enough.
A.2 PROOF OF LEMMA
Lemma Let 2 Then, for any continuous function f R + Rd, any compact set K. C Rdd and any E > 0, there erist time T E R and a piecewise constant imput (A, (A,WDD) b) [0, + Raxd Raddd x Rd so that the flow map o² associaled with the newral ODE salisfies: || o" (L S..
Proof. This is a special case of Theorem 2.3 in Li et al. 2022
A.3 PROOF OF LEMMA 10
Lemma 10. If the parameters (A,WDD) are piecewise constants, then for any compact set K and any > 0, there is leaky-ReL Reayy-ReLC 0 network fr (x) with width d and depth L such that
-x S Vr e K.
(8)
Proof. is Theorem 2.2 Duan et al. (2022
A.4 PROOF COROLLARY
Corollary 11. Let K. C. Rd be compact set and d 2 2; then, for the function class Rd), the Baky--ReLl networks with width d have LP-UAP.
Proof. For any f*(x) E LP(K, Rd) and & >>> 0, there is flow map oJ (x) associated with the neural ODE 33) such that (according to Lemnma 9
(+) o5 (1)lor 2
Then, employing Lemma 10 there is a leaky-ReLU network ft. such that
[15x(-) - o² (.)l S
Therefore, we have
(l)(() (' S (1/(()) क7 Z.)lzz + (15(() or (-)llo Se.
13

---

Published as a conference paper at ICLR 2023
B PROOF OF THE MAIN RESULTS
B.1 PROOF OF LEMMA
Lemma 1. For any compact domain K. C Rd and any finite set of activation functions (o,), the {or} networks with width w "iin max(d2, do not have the UAP for both (PC,RR) and C(C,R*.)
Proof. It is enough to show the following two countercxamples (*) that cannot be ap- proximated in the LP-norm.
1) (xx | less than de - In fact, we can relax the networks to a function f'xx) = of + b), where Wx b is a transformer from Rd to Rd and o(x) could be any function. A consequence is that there exists a direction (set as the vector satisfying We 0, ||||| 1) such that f(z) f(x Av) for all X R. Then, considering the sets {x | 0.1} and
= 2)d,, cannot be approximated by any nerssrks with widths
B = fx: 1| - all s 0.1), we have
1 (f(x) - (x)lde
S (1((e) -
[f(x) (x))
2 f (1(())) -xx)) u1 fr v)l)
J (1)())) (+ 0.8|A|.
Since the volume of A is fixed positive number, the inequality implies that even the L approximation for f impossible. The case of the L norm and the uniform norm is impossible as well.
2) The function fr, the parametrized curve from to along the edge of the cubic, cannot be approximated by any networks with a width less than dy - 1. Relaxing the networks to function f(x) W*(()) + b, vxx)) could be any function. Since the range f is in hyperplane while f* has positive distance to any hyperplane, the target f cannot be approximated.
B.2 PROOF OF THEOREM 2
Thcorem 2. Let K. C Rdd be a compact set; then, for the function class LP Rd:), the minimurn width of leaky-ReLU nelworks having LP- --UPP P eraclly Wmin max dyy 2).
Proof. Using Lemma we only need to prove two points: 1) the LP-UAP holds when max dy) 2 2, 2) when d, = dy = 1, there is a function that cannot be approximated by leaky-ReLU networks with width one (since width two enough for the IP-UAP)
The first point is consequence of Corollary 11 since we can extend the target function to dimension max(d2. dy).
The second point is obvious since leaky-ReLU networks with width of one are monotone functions that cannot approximate nonmonotone functions such as f (x) x²,x E [-1,
B.3 PROOF THEOREM 3
Theorem 3. Let C dd be compact set; then, for the function class PPK,, the min- imum width of leaky-ReL RRcth---LUAABB. networks having LP-UAP is eractly wmin = max(d2, dy).
Proof. This is a consequence of Theorem (for the case of maxx(dr. dy) 2 2) combined with Lemma (for the case of d. dy 1).
14

---

Published as a conference paper at ICLR 2023
B.4 PROOF OF LEMMA
Lemma 4. Let K C -d= be compact set; then, for the function class C(K,R4y) the min- ireu width of ReL.U+FLOOR networks having C-UAP is eracily Wmin max(da, 2, d,y).
Proof. Recalling the results of Lemma 1 we only need to prove two points: 1) the C-UAP holds when max(d,, d,) 2 2, 2) when dg dy 1, there is function that cannot be approximated by ReLU+FLOOM networks with width one (since width two is enough for the C-UAP).
The first step can be constructed by the mnooder-memorzzer--eddd approach. The second point is obvious since ReLU+FLOOR networks with width one are monotone functions that cannot approximate nonmonotone functions such as f (z) x² E [].
B.5 PROOF OF THEOREM 5
Theorem 5. The UOE networks with width dy have C-UAP for functions in C((O, 1),
Proof. Since functions in C((0, 1]. () can be regarded as dy one-dimensional functions, it enough to prove the case of dy 1, which is the result in Lemma
B.6 PROOF COROLLARY G
Corollary 6. Let K C Rd be compact set; then, for the continuous function class C(K.R%:) ) the minimum width of UOE+FLOOR networks having C-UAP is eractly Wmin max(dz,d)) dy).
Proof. The case where max(da, dy) 2 2 is consequence of Lemma since the UOE function contains the Peaky-ReLU part. The case where max(da, dy) 1, i.c. dy dy 1, consequence of Lemma
15


Reviews:
[{"review_id": "l9mDdKIgAY", "reviewer": "Reviewer_Mii1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThis paper builds on certain recent results on Neural-ODE way of approximating functions and gets sharp estimates on the width required for feed-forward nets to approximate continuous and Lp spaces over compact domains. ", "summary_of_the_review": "I think the paper needs some significant improvement in the presentation clarifying the issues raised above and my rating essentially reflects that. ", "strength_and_weaknesses": "The two highlights of their results is that (a) they are able to get a sharp estimate of the width requirement for space of continuous functions mapping between two unit cubes in different dimensions.  And (b) they have a very interesting approach to these width estimation problems via recent results in Neural-ODE. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fMFjkwkZuPi", "reviewer": "Reviewer_emi4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the universal approximation problem of functions using neural networks. They showed that, the minimum width to approximate any functions in $L^p(\\mathcal K, \\mathbb{R}^{d_y})$ and $C(\\mathcal K, \\mathbb{R}^{d_y})$ is at least $w^*_{\\min} = \\max (d_x, d_y)$ for any activation functions. Furthermore, they showed that for some specific activation functions, such as Leaky-ReLU or ReLU+FLOOR, the minimal width can be achieved. ", "summary_of_the_review": "The main result, which states that for any activation functions, the minimum width of a DNN to approximate any functions in $L^p(\\mathcal K, \\mathbb{R}^{d_y})$ and $C(\\mathcal K, \\mathbb{R}^{d_y})$ is at least $\\max (d_x, d_y)$, is an unexpected and elegant result, which is a non-trivial extension of previous results in this field. ", "strength_and_weaknesses": "The related works are adequately cited. The main results in this paper will certainly help us have a better understating 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. The main result, which states that for any activation functions, the minimum width of a DNN to approximate any functions in $L^p(\\mathcal K, \\mathbb{R}^{d_y})$ and $C(\\mathcal K, \\mathbb{R}^{d_y})$ is at least $\\max (d_x, d_y)$, is an unexpected and elegant result, which is a non-trivial extension of previous results in this field. It would be more interesting if the authors could study the exact minimum width for more activation functions and more architectures used in practice. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cWCFmO_CWw2", "reviewer": "Reviewer_Vm8T", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The script studies the minimum width of neural networks to achieve universal approximation. Similar topics are also extensively studied in Park et al. 2022.\n", "summary_of_the_review": "1. I doubt the significance of the script compared with the existing work Park et al. 2022. I compare the results as follows.\n\n**As for the lower bound:** the script provides a lower bound for arbitrary activation, which extends the results in Park et al which focuses on ReLU. \n\nPark et al. : w_min >= max (d_x +1 , d_y), ReLU\n\nThis script: w_min >= max (d_x , d_y), arbitrary activation\n\n\n**As for the upper bound:** both the script and Park et al. construct neural networks to match the lower bound. \n\nPark et al. : w_min < = max (d_x +2 , d_y+1 ), using general activation\n\nThis script: w_min < = max (d_x , d_y), using Leaky-ReLU+ ABS. \n\n\nFor both the upper and lower bound, the script improves the results in Park et al. only by constant 1 or 2. I doubt the significance of such improvement, please clarify the importance if there is any.\n\n\n\n2. The most important theoretical result is Theorem 2. However, the relevant analysis (the neuron ODE part) is mainly based on  Li et al. 22 and Duan et al. 22, please clarify the novelty if there is any. \n\n\n3. The definition of C-UAP and Lp_UAP is missing\n\n\n++++++++++++++++++ **POST REBUTTAL** ++++++++++++++++++++++\n\nThanks for the reply from the authors. Regarding my question 1, I am still not convinced about the importance of this result compared with the upper and lower bound of Parker et al.. I will keep my score. \n", "strength_and_weaknesses": "The presentation needs to be improved. For instance, many terminologies such as C-UAP are not defined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7DYq_axa01", "reviewer": "Reviewer_VMbe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tightens the upper bound from Park et al. (2021) while also proving a corresponding lower bound and prove that both $C-$UAP and $L^p-$UAP for functions on compact domains share a common minimum width $w_{min} = \\max(d_x, d_u)$. In fact, they use some tools from Neural ODEs to show that the critical width for $L^p-$UAP is achieved by leaky-ReLU networks.", "summary_of_the_review": "I have a few minor concerns and clarifications as mentioned above. If they are resolved, I would recommend acceptance. I think it is a good contribution to a line of work which has a rich history.", "strength_and_weaknesses": "**Strengths:**\n- They prove matching upper and lower bounds, tightening the bound from Theorem 4 in Park et al. (2021) while also closing the problem of $L^p-$UAP.\n- The paper is well written with clear proofs.\n\n**Weaknesses:**\n1. I think Table 1 should also include Theorem 4 from Park et al. (2021) which shows that $w_{min} \\leq \\max(d_x+2, d_y+1)$ for continuous non-poly activations. If I understand correctly, the main contribution of this paper is tightening that bound and proving a corresponding lower bound which Park et al., were lacking. Please correct me if I am wrong.\n2. The definition of UOE functions should be stated (atleast intuitively) much earlier in the manuscript as it is mentioned several times.\n3. I would rephrase Lemma 11 as a corollary since it follows directly from Li et al., and Duan et al.'s results. That said, it is a nice connection that proves this result quite easily. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster