Expressiveness of Neural Networks Having Width Equal or Below the Input Dimension
Authors: Hans-Peter Beise
Steve Dias Da Cruz
Venue: ICLR 2022 Submitted (2022)
Keywords: Neural network approximation
expressiveness of width bounded neural networks
maximum principle

Abstract: The understanding about the minimum width of deep neural networks needed to ensure universal approximation for different activation functions has progressively been extended \citep{park2020minimum}. In particular,  with respect to approximation on general compact sets in the input space, a network width less than or equal to the input dimension excludes universal approximation. In this work, we focus on network functions of width less than or equal to the latter critical bound. We prove a maximum principle from which we conclude that for all continuous and monotonic activation functions, universal approximation of arbitrary continuous functions is impossible on sets that coincide with the boundary of an open set plus an inner point. Conversely, we prove that in this regime, the exact fit of partially constant functions on disjoint compact sets is still possible for ReLU network functions under some conditions on the mutual location of these components. We also show that with cosine as activation function, a three layer network of width one is sufficient to approximate any function on arbitrary finite sets.

Under review as a conference paper at ICLR 2022
EXPRESSIVENESS OF NEURAL NETWORKS HAVING WIDTH EQUAL OR BELOW THE INPUT DIMENSION
Anonymous authors Paper under double-blind review
ABSTRACT
The understanding about the minimum width of deep neural networks needed ensure universal approximation for different activation functions has progressively been extended (Park et al., 202T). In particular, with respect to approximation general compact sets in the input space, network width less than or equal to the input dimension excludes universal approximation. In this work, we focus network functions of width less than equal to the latter critical bound. We prove a maximum principle from which we conclude that for all continuous and monotonic activation functions, universal approximation of arbitrary continuous functions is impossible on sets that coincide with the boundary of an open set plus inner point. Conversely, we prove that in this regime, the exact fit of partially constant functions on disjoint compact sets is still possible for ReLU network functions under some conditions on the mutual location of these components.
INTRODUCTION
In the course of the increasing popularity of deep neural networks for applications in technical, ecological and many other fields, there has been huge progress in the research on understanding the mathematical properties of the mathematical mapping implemented by a deep neural network. The approximation properties, expressiveness, of neural network functions have attracted intense interest. The central result in this field is the classic universal approximation theorem, which states that any continuous function can be approximated with arbitrary accuracy (in terms of uniform approximation or T.p norms) by neural network functions that have only one hidden layer for nearly every activation function (Cybenko 1989 Hornik 1991). recent years, these kind of results have become more precise, for instance, in terms of estimates on the order of magnitude of parameters needed to achieve an approximation of a certain accuracy (Petersen & Voigtlaender [0188] Yarotsky 2017 2018) 8) or by investigating the number off piece-wise linear regions (Montular et al. 2014 Serra et al. 2018 Hanin & Rolnick] 2019); we refer to Vore et al. 2020) for an overview on recent developments. Since empirical observations showed that depth has significant impact on the performance of neural networks, a lot of research has been dedicated to the effect of depth on the expressive power of neural networks (Telgarsky] 2016)] Mhaskar & Poggio 2016 Montufar al.] 2014, Raghu et al.) 22177 Rolnick & Tegmark| [0018] Lin et al. 2017
et al. 2016)) Besides this. the role of width expressiveness of network functions has been investigated (Lu et al. 2017 Hanin & Sellke, 2017 Hanin 2019 Johnson 2018 Kidger & Lyons 2020 Park et al. 2021). An important
result states that width larger than the input dimension is needed allow universal approximation on arbitrary compact sets. It has also been shown that the capability to learn disconnected or bounded decision regions depends on whether the width is larger than the input dimension (Nguyen et al.. 2018 Beise et al. 2022I.
In a further line of research, the capabilities of neural networks to memorize finite sample sets is investigated (Yun et al., 2019 Vershynin| 20200] Bubeck et al. [220 Park et al. 2020). which provides mathematical foundations to the surprising findings that neural networks can interpolate the training data (Zhang et al. 2017) in practise.
In this work, we investigate what kind of subsets M C R admit universal approximation by neural network functions with a maximum layer width less than or equal to the input dimension, i.c. network functions that violate the necessary condition for universal approximation given in Hanin (2019) and Park al. (202)) for arbitrary compact sets. sets.

---

Under review as a conference paper at ICLR 2022
Let us introduce the following notation: For a set D C IR we denote by D the set of interior points, by D its closure and by 0D = D' \ D the boundary of D. By II-Il we mean the Euclidean norm. For linear subspace U RR, we denote by dim(U) its dimension and by Pe R" - U the orthogonal linear projection on U. We denote by ej the unit vector of the j-th coordinate axis in R For some V E I2" and j E nl,... we write e for the j-th component of U.
For some depth L E N. we consider neural network functions of some, F: R R where no is called the input dimension and ny the output dimension. Our network functions have the following form
F = WL(AL-1 A1) + br.
(1)
where A,(x) = oW, b,) with W E R" (weights), by E R (bias). where j = 1, L. and a > R the activation function. The application of a and the inverse image 0- are understood to be applied element wise to vectors or subsets of IR". The widely used activation function rectified linear unit, shortly ReLU, defined by t + max(t, 0}. As a shorthand notation of the function implemented by the first & layers of network function, we set
Fg W (Ax-1 A1) + by:
for ls E [I...., ..... L 1}. We call n2 the width of layer 1, I,.., L. The width of the network is defined as (FF) = max(n, == 1, I.., } and L is called the depth of the network. For m, E N and an activation function a, .N (m, L) is the set of network functions F : R + IR* of the form with activation o and of maximum width m, i.c. w(F) S m, and depth L. i.c. L layers including the final linear layer. In case that R R we omit the latter and write NN L) instead, and in case the the depth is not specified, meaning that arbitrary depth is allowed, we write NN (m), NN a (m), respectively.
We say that compact subset M C R admits universal uniform approximation of functions in some function class of mappings from M to by network function of NNN, (m, L.) or N. ( (m), for every MM + R in that class and every E >> O, there cxists some F E NN (m, L), respectively F E N'N (m), such that
max #EM
(f() F(+))((())) <E
2 RELATED WORK
Approximation properties of width bounded neural networks have been studied in several papers. A common goal in these lines of research is to provide upper and lower bounds on the minimum width of the network, i.c. the minimum number of neurons per layers, here denoted by Wmin. needed for universal approximation in C(M, R"*), ), í.e. the space of continuous functions from a compact set M to R endowed with the norm of uniform convergence, and (M,, R**) with some set M R iee the space of functions f - (fi,..,, fn.)) from M to IR= such that every |fy I2 is integrable over M, endowed with the usual Lp norm. Since in this work are interested in universal approximation in C( M, IR), we refer to Lu et al. (217). Kidger & Lyons (2020) and Park et al. (2.2 1 for the case of Lp approximation. For the case of C C(M, ",), it was proven in Hanin & Sellke (2017) that
no + 1 S wimin E no + ni, for ReLU activation,
(4)
which has been tightened in Park et al. (2021) to
Wmin max(no 1, 32 for ReLU and STEP activation,
(5)
where STEP refers to the threshold activation that maps to on (a 2 0} and 0 otherwise. It has been shown at the same time in Johnson (2018) and Beise et al. (20T)) that
Wmin 2 mo + for ReLU + iijectivee continuous activation.
(6)
The activation functions allowed in Johnson 20188) are slightly more general, as it is only required that they admit arbitrary accurate uniform approximation by injective continuous functions on arbitrary compact subset of IR. In Kidger& & Lyons (2020) the above upper bounds are extended to further classes of activation functions. For these results and a general overview on recent developments in this field, we refer to Park et al. (2021). As we also formulate results for finite sets, our work partially exhibits relations to the research on finite sample memorization (Yun et al. 2019 /eeshynin 2020
Bubeck et al. 2020 Park et al. 2020).
2

---

Under review as a conference paper at ICLR 2022
In this work, only consider width less than equal Ro and investigate uniform approximation on certain compacts subsets of the input space. According to the above result (6. we cannot expect universal upproximation for all compact M C Ro However, common assumption in applications that approximation is only needed on a certain subset. We derive some topological conditions on M that allow or exclude kind of universal approximation under these cireumstances. Although narrow neural networks, as they are considered in this work, are not common in practical applications, many networks exhibit decaying layer width at the later layers. From this perspective, our results give theoretical insights on the kind feature extraction earlier layers need to implement in order to allow the later layers solve given machine learning task. Our main contributions are as follows:
1. A maximum principle is given for F E N (ma) with a continuous and monotonic. This allows to conclude that the lower bound Wmin 2 nip + 1 in (6) is sharp for a wide range of subsets M, e.g. when M aD U {c} for some D with non-empty interior and D
2. We show that for the of two disjoint compact sets, the existence of cone-like sector that contains one of these sets and does not intersect with the other one, is sufficient to allow exact fit of functions that take constant values on each of these sets by network functions from N ReLU (No, 4). A weaker result is concluded for the case of multiple pairwise compact components.
MAXIMUM PRINCIPLE
Let us recall that NN e (mg) designates the set network functions with activation function o, having maximum width no and arbitrary depth. In this section, we will prove a maximum principle for network functions of NN (no) for a wide class of activation functions. This principle can be viewed root cause why universal approximation with functions from NN, (ng) on arbitrary compact sets is impossible as shown in Johnson (2018) and Beise et al. (202T), see (6). This also immediately leads topological condition on subsets of InD that do not admit universal approximation by functions in N o (no).
Theorem (Maximum Principle). Let M be some compact subset of Re and a a continuous, monotonic activation function. Then every F oNNo1o takes its maximum value the boundary OM.
Note that, considering F instead of F, the latter result also implies that the minimum value is taken on 0M. This implies that universal uniform approximation of continuous functions is impossible on compact sets with non-empty interior. Even more, it can be concluded that:
Let M be some compact subset of "o such that aD C M and M D + 0 for some non-empty open set D R Then M does not admit universal uniform approximation of continuous function by network functions from NN, (no).
Corollary 1.
The latter results naturally lead to the following question: Is possible to uniformly approximate arbitrary continuous functions on the unit sphere (in Th with arbitrary accuracy by network functions as they are considered in Theorem I Some positive approximation results are given in the next section, but a gap to an answer to the question remains.
is not clear to us whether the conditions Theorem T can be weakened a way that it also applies to network function having width larger than the input dimensions under certain circumstances. The following might be a natural question in this context: Let F Ro + R be a neural network function of arbitrary width but with weight matrices having rank less than equal to nig Does maximum principle similar to Theorem apply in this case? The following example shows that the maximum principle in Theorem does not hold in this case.
Example 1. Let M [-1, 1] and let W1 g2x1 and bj R22 implement the following linear affine mapping
Wa + by = I (1+1)
Then Mj = M + by) is given by Mi = M1,1 U UM22 where
Mr, ((x 1, : E M, and 0}
3

---

Under review as a conference paper at ICLR 2022
2 :
xx M, I 2 0}.
Now, v (1,1/2) E R., W2 E 1222 and by E R² such that I H W22 + b2 implements the orthogonal projection onto the hypersurface V := {x E² x²v (),)) That is, the hypersurface orthogonal to which intersects (1,0) Then both, M1,1 and M1 are mapped the line M2 : {y E R² y (1, () + S X < 1/2) and since those vectors are contained the first quadrant we have
M2 = ReL ReLU(
+.) +
It can further easily be verified that, under the latter two layer network function, O, which is an inner point of M, is the only vector that is mapped to the extreme point (1,0) of M2. Now it is easy to find a weight W3 E R22 such that the linear map x + Wyx as mapping from M2 to R takes its minimum or maximum value at (1.0) only.
By concatenation of additional components the input dimension such that M =--1111) x [0, 1|a. E N, and adaptation of the weights W1, W₂ and bias b, by in a way that these additional components are mapped identically under the action of the layer network function ReLU(W + b1) + b1), the above example can be extended to higher dimensions.
The following proposition provides the main observation for the proof of Theorem
Proposition 1. Let M be a compact subset Ro a continuous, monotonic activation function and F E No (na) such that all weight matrices W,, j 1.... L, are square and have full rank. for some x E M the image Fxx) is a boundary point of F(M), i.e. F(x) E (F(M), then there an ā E aM such that F(t) = F()).
Proof. In case that a is injective, the whole network function F is injective since the weight matrices assumed be square and of full rank. Hence, the invariance of the domain theorem gives that no x E M can be mapped to @F(M). The remaining case is that a is partially constant. Then, given x E M with F(x) E @F(M), let l be the smallest k E {1,..., I. - 1} such that (1)) E do (M)). Notice that such a k must exist since, according to the invariance of the domain theorem, the last injective, linear affine mapping x ++ WL. cannot map inner points to boundary points. Then, necessarily for at least one component of (z). partially constant part of is active. More explicitly, say (F)(z)) E Jaj,by by] R with (t) = Cj. where ej is the constant value taken for all intervals can be enlarged arbitrarily to either (0).00) or (-00, by]. which would be the case for ReLU activation, we can find E R such that dg = P1(x) +ej E (M) and with (1gg) In a next step we show that such an vg can also found in cases where the length of the intervals (ay, by] are upper bounded. In those cases we may assume that the intervals (ay, by] are maximum in the sense that at their left and right end a is not constant any more, and is maximum in the sense that for every other index, the activation function is injective in neighbourhood. Indeed, such components would not exist, the component wise application of a would be injective in small neighbourhood of (x) and the invariance of the domain theorem would exclude that (Fx(x)) E Oo (M)). . By the selection of k, (x) is still an inner point of Pg(MM, The fact that the inner point F2 (x( (FF is mapped to boundary point by the element wise application of implies that there some non-empty
byl. for some indices E IIC C {1. .... }. In case that one of those
or (x)).
with corresponding ty such that
ty E (=((((=))) + aj. (Fi(z))() + b,y. jei
(7)
t :2:= + ΣGe, (M).
(8)
jet
Indeed, otherwise,
mg
P₂(x)
Σ 1=1
Lee E (Fa(M))
where for some small > 0 and all E I, lj may be chosen arbitrarily in (-(Fg(x)) +aj
E, (F)()))) + by E) and |t,l 0 for j & T. By the definition of 7 and the corresponding
4

---

Under review as a conference paper at ICLR 2022
intervals lag. byl, this would imply that (F)( is inner point of a (F) Now, 8 implies that there is a E M such that
= = + Σ teg E (M),
with ł as in (7). Considering that W is square and has full rank, the inverse image of (i( under - Wa: g 0g is boundary point of ( in case that > and a boundary point of M in case when 1 = 1. In the last case we are done. In the first case, the same reasoning can be applied to I instead of x, and the iterative application finally leads to a boundary point of M that is mapped to (F)( = a (F)( and hence follows the same trajectory when passed through the last layers from k to L.
Proof. (Theorem T may assume that M is non-empty and that every weight matrix W j == i,,,.., 1, is square and of full rank. Otherwise the result is trivial, because F(M) (F(M Hence the assumption of Proposition holds Wræ from TR to IR takes its maximum and minimum values @F(M), the latter proposition also implies that F takes its maximum value on a.M.
holds for F == AL-1 ... A1. Since the linear mapping
4 APPROXIMATION PROPERTIES ON SUBSETS
In this section give some approximation results that show that, despite the limitations induced by Theorem T the network functions considered in this work still allow some weaker kind of subsets. The first result in this section follows from existing results approximation by network functions. The first point can be deduced from Hanin & Sellke (2017) Theorem 1). The second point be derived from Hanin & Sellke 2017 Proposition 2) or from Hardt & Ma (2177) proof of Theorem 3.2.).
universal approximation
Proposition 2.
1. Let M be some compact subset of R If there exists a subspace C g with dim(U') < no such that Py is injective as a mapping from M to U. then M admits universal uniform approximation of contimuous function by network functions in NN BeLU (dim(() + +1).
2. Let M = =xI,,.., Im & C. Ie be a finite set and f M + IR some mapping. Then there exists a network function F N NNLuu such that F(x) = f(x)) for all M.
The proof is almost straightforward, given the results from the aforementioned works. proof can be found in the appendix.
We next extend the second statement of the latter proposition the case of two disjoint di-dimensional compact sets. Theorem | shows that arbitrary uniform approximation is not admitted on such domains. However, exact fit is possible for functions that are constant on each of these sets under certain geometrical properties on their mutual location. The approximation of such functions arises naturally classification tasks where each point in a particular disjoint compact set belongs to the same class, ic. these sets constitute different disjoint clusters of the data.
Theorem 2. Let M K1 U K2, with disjoint compact sets K1, K₂ C -80 such that for some c E Ro and some linearly independent U1, Ung goo the set K₁ is contained in the sector
no
s ::= = Σ Aoy,, > 0}
1=1
and K2 C. R 33. Then for every function f: M - R that takes constant values on K₁ and K2, respectively, there exists a network function F E "eRRuuuo,, 4) such that
f(x) F(x)
for every M.
5

---

Under review as a conference paper at ICLR 2022
The conditions of Theorem 2 are verified and inspected by numerical experiments in Section 6 How- ever, to us it is unclear whether the assumptions on the mutual location of the compact components in Theorem 2 can be significantly weakened. Increasing the depth will certainly allow more complex configurations. However, from Theorem is clear that K₂ cannot completely enclose K when the maximum width is upper bounded by no. matter how many layers the network contains. We think that closing the described gap could entail important insights for the theory of neural networks.
For the proof of the latter result we need the following.
Proposition 3. Let K, M be two compact sets in Ro that are strictly separable by a linear hyper surface. Then there exists F E NNN ReLu (no, 2) such that F(K) is single vector in R M and F(x) = x for all x E M. Moreover, F can be arranged in a way that given & > 0
min|| F(K) - x=| < E. zEK
As a consequence of Proposition 3 and Proposition 2 we obtain the following for the case of more than two distinct sets under considerably more restrictive condition as in Theorem 2
Corollary 2. Let M - K5 with pairwise disjoint compact sets K₁ C [R",, 1,.., d such that for every K3 there exist Dy wh and q₃ R such that
uf x > 9j for all Kj, and ui x=== < 93 for all x E M \ Kj: i.e. there are linear hypersurfaces separating each Kj from the remaining K₁, 1 + Then for every function f M + R that takes constant values on every Kj, j 1,.., d. there exists a network function F E NNN (no) with
f(x) F())
for every M.
2 By means of Proposition) we find an Fi E N (mo) such that Fi (x = for x E - K, and a == Fi (Ki) is a single vector in IR" \ - Kj. Proposition also allows us to choose Fi in way that a₁ is sufficiently close to K₁ that the conditions of Corollary 2 still apply U K3 U {a1}. We can iteratively apply Proposition to find f..,...A Fa E N ReLu (no)
Proof. (Corollary
such that
Fa o..... o Fi(K)) = ay. j 1,....d d
for pairwise distinct a1,... Od E Ro Now, for a given f M -> I with f(x) = yy for all x E Kj. j 1,..., d, Proposition yields an F NNN (2) (2 desired network function is then obtained by F = F Fa c..... F1.
with F(a,) = yj for all j = 1,.., d. The
Proof. (Proposition 3) Let us remind that E1, eno are the standard basis vectors in R By assumption, there is a v E R with [|e|] 1 and q E E such that o'z > q for x E K and v" x < q for x E M. For a given e > O we may assume that the linear hyper surface defined by I1 := far E 18 v" = }} is so near to K that for some a K that realizes the minimum distance of K to H we have
(9) Indeed, otherwise we can shift the hyper surface accordingly by increasing q. Then, by the fact that ||a|| 1, (9) means that has distance equal e/2 to H and ă a E/2v H is the unique vector in that realizes this distance. Let V/2 E R xno such that x +> Vix implements a length preserving rotation that maps
vf = +
ei Then x + V1 Viā maps H span(e2, eno) and Ki = V-K- - V is contained in the half space of vectors with negative first component and with aj : Via Viā -/22 e,, and M2 = V V is contained the half space of vectors with positive first component. By compactness of K1 and M1. we can find .... Uno E span ..., eng such that for a > U1 dei.... Uno de; are linearly independent and such that with sufficiently small
no
K, ST == fx R to
Σ Ay(- de1), 2, > 0}
1=1
Mj C S+ = (x E
R no x
Az(u, + +5cz), 2, > 0).
==1

---

Under review as a conference paper at ICLR 2022
Let V22 E R such that >> V22 maps -, deι -c for j I.., Ng. Then, by linearity, every U, + de₁ is mapped to e; for = I.... Rg. Thus S is mapped to the cone of vectors having negative components only, and S is mapped to the cone of vectors having positive components only. Hence, the application of ReLU maps all of 12 to O and maps V2M1 identically. We can now apply the inverse of the linear affine mappings which will map V2 back to M, i.e. for
F(x) == Vi= V/2 (e2 Vıā)) + a.
With this F we have F(M) = M and F(K) = F(a) = ã. Note that by 9 and the definition of ä minl|æ F(a)ll = e/2 <
=EK
which concludes the proof.
Proof. (Theorem 2 Let V be the matrix that results from the concatenation of the columns V1, ..., Uno and set W1 V-1 and bj W (-c).. Then the mapping x: + Wix maps the vy to -Cj- j = I,.., no and W, Ki + bi is a subset of
Ro
S = fa n0
Σ
(((-)))
and Wi K2 + b, C R
55. Thus, the one layer network function Fi(x) = ReLU(Wir b1) maps all x E K1 to 0 and x E K2 are mapped to
{ E Ruo x Σ Xee, A 2 03 (0).
Hence, with a sufficiently small q > O, Fi(K)) and Fi (K2) are strictly separated by the linear hyper surface
f Rm (1, I,... 1)x q).
The twofold application of Proposition 3 yields two network functions that can be concatenated to ReLt (no, 3) with F2 Wa ReLU(('s ReLUU(22x: are two distinct vectors u1, U2 in R
three layer network function F2 N
b2) + by) + by and such that (F (K))) and (2(FF respectively. For given f M - R that takes constant values K₁ and K2, say 01 02 R, respectively, we attach a linear affine layer + w" x + by. where w E 1"" by E IR such that w un + by = ai and wt u2 by d2. This mapping is integrated in the final layer of F2 Fi and finally gives
F(x) w TW W. ReLU(W, Re.u ReLU + +b) + b2) + bs) + w ba + bs.
We conclude this section with a comment on implications of our results on generalisation. In Zhang al. (2017) the researchers made the observation that deep neural networks can interpolate randomly annotated data, which shows the enormous capabilities of large networks to memorize data. In Proposition Theorem 2 and Corollary 3 we show that network functions of width less than equal than to input dimension in many configurations also implement an exact fit of the training data. At the same time these network functions restricted by the maximum principle given in Theorem [ which may contradict the underlying distribution of the data at hand.
5 UNIQUENESS
maximum principle similar to Theorem [ aasso applies for harmonic and holomorphic functions. that is, the null space of the Laplace operator and the null space of O := 1/2(0, + i0,)) (æ real part, y imaginary part), respectively (Rudin) 2006). As consequence, uniqueness theorem applies which states that two harmonic, respectively holomorphic, functions coincide on the interior of given set when they coincide on its boundary, respectively. In view of Theorem it is hence natural to ask whether a similar result applies in the case of network functions in N a (Ro). However, the proof for the case of harmonic and holomorphic functions relies on the fact that these functions form vector space, which is not the case for the set A/W, o (no). The following examples show that uniqueness theorem does not hold, in general, for the network functions with (strictly) monotonic activation functions considered in this work.
7

---

Under review as a conference paper at ICLR 2022
Example 2. Let a (x) be the leaky ReLU function defined by a (z) x: for 2 0 and (x
for x < O with a > 0. Then
1 (1+a)oa(1++
a (1 a and a + 0a Galzon (2 +
x x
both map - -1 and to but the first one maps 0 to a + a), while the second one maps 0 to 1/2 and hence do not coincide unless 1.
Example 3. A similar example can be obtained for analytic activation functions. Indeed, let a be the sigmoid function. For ++ a(a + b), one can arrange a O, and b E R, such that in one case only a concave and in second case convex excerpt of sigmoid is active for x in [0,1], respectively, and such that both functions coincide at and As the first one is concave and the second one is convex on [0,1] and both are non-linear, they do not coincide on the interior of [0.1].
A simple uniqueness result follows from the following observation.
ReLu Proposition 4. Let M be a compact subset of R F E N (no) and B = B=F the inverse image of the inner points of FMM). Then F is linear affine and bijective mapping from to (F).))
((F(M)))
proof of Proposition iss given in the appendix. As consequence we have.
Corollary 3. Let F, G,G N (eLLv(n)) and M C Re0 be some compact set. If F and G coincide on a set of vectors 01 mrry Ung in
K = F= (GE(M))))G
such that Di - Uno+1 j = 1, n2g are linearly independent, then F(z) = G(z) for all x E K.
should be noted that in the latter corollary, the fact that F, G coincide on K does not imply that F and G are the same network functions as functions on TR
6 NUMERICAL EXPERIMENT
We provide numerical results to illustrate that neural networks learn transformations similar to the construction of our theoretical derivations in the proof of Theorem 2 We formulate a toy example consisting of several (6 or 8) pair-wise disjoint balls of the same class encasing center ball of a different class. The border balls use a radius of 0.125 and subset of the centres (0.25, 0.25), (0.5, 0.25), (0.75, 0.25), (0.25, 0.5). (0.75, 0.5), (0.25, 0.75), (0.5, 0.75) and (0.75, 0.75) while the center ball uses a radius of 0.01 and the center (0.5, 0.5). We generated randomly and uniformly 2000 data points for each border ball, however, as the classes would hence be unbalanced, we generated as many data points for the center ball as there are in total for the border balls. We used a multilayer perceptron (MLP) consisting of 4 layers, all of width and the ReLU activation function (as stated in the theorem). For illustration purposes, we used an input dimension of 2 such that the neural network functions of the form F N (2). We used batch size of 16, the Adam optimizer with a learning rate of 0.001 and we trained each model for 500 epochs using the mean mean-squared squared error (MSE) our cost function. The different datasets and results are reported in Fig. [ We rate an experiment as successful when the universal uniform approximation condition (3) tends to zero. It can be observed Fig. [ (a) that, when the conditions Theorem are fulfilled, the neural network can approximate the function correctly and the different layers are learning transformations similar to the constructions the proof. When the conditions are violated, as is shown in Fig. (b), the universal uniform approximation condition does not tend to zero and the intermediate layer transformations need to violate the constructions in the proof. Additional results are reported Fig. 2 in the appendix.
7 CONCLUSION
We identified maximum principle that holds in the case of width less than equal the input dimension for all common activation functions, which can be interpreted as a root cause why universal approximation is not possible under the aforementioned conditions. On the positive side we proved
8

---

Under review as a conference paper at ICLR 2022
dchatie Laverta
Lane Ediazie PAEO Lave 56
54
-45
52
34
SAU Liwrab
0.30
01
0.00
07
0.00
041
0.5
E30
000
008
830
63
-53
-22
+01
00
60
82
0.8
0.68
0.15
0.13
0.8
00
10
(a) 7 border balls center ball radius: 0.01 MSE: 0.0 UUAC: 0.0
Letr
422
00
04
(b) 8 border balls center ball radius: 0.01 MSE: 0.01135 UUAC: 1.08494
Figure 1: Datasets (a) and (b) together with the learned transformations by each activation function and layer. When the conditions of Theorem 2 are fulfilled (a), the transformations are similar the construction in the proof. Otherwise (b), the construction in the proof is violated. We report the final decision regions, the mean-square error (MSE) and the universal uniform approximation condition (UUAC). Each subplot's title describes the function which was applied to the previous subplot's 's data.
that, although being not sufficient for universal approximation in the general sense, ReLU network functions of width less than equal to the input dimension are sufficient to implement functions that give zero or arbitrary small training error in some machine learning tasks. In particular, we have shown that for the case of two disjoint compact sets, exact fit in a two class classification task is feasible with 4 layers, provided the sets can be separated by a cone like sector. However, there remains gap between our positive results and limitation implied by the maximum principle. Our numerical experiments show that neural networks learn transformations similar to our theoretical derivations.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
This paper is a contribution to the theory of neural networks, which includes some numerical examples illustrate our findings. For this purpose, we work only with artificial two-dimensional data and simple network architectures, each of which is described in detail and is therefore easily reproducible. Further, we provide a code implementation in the supplementary material to reproduce the results of our paper. A proof is given for all the theorems, propositions and lemma either in the main paper or in the appendix.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hans-Peter Beise, Steve Dias Da Cruz, and Udo Schröder. On decision regions of narrow deep neural networks. Neural Networks, 140:121-129, 2021.
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint arXiv:2006.02855 2020.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on Learning Theory (COLT), pp. 698-728, 2016.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
Ronald Vore, Boris Hamin, and Guergana Petrova. Neural network approximation. arXiv preprint arXiv:2012.14500 2020.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics, 7(10)999,, 2019.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. 2019.
Boris Hanin and Mark Sellke. Approximating continuous functions by ReLU nets of minimal width. arXiv preprint arXiv:1710.11277 2017.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations (ICLR), 2017.
Kurt Homnik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251-257, 1991.
Jesse Johnson. Deep, skinny neural networks universal approximators. In International Conference on Learning Representations (ICLR), 2018.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on Learning Theory (COLT), pp. 2306-2327, 2020.
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work well? Journal of Statistical Physics, 1236-1122 2017.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6232-6224422 2017.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829-845 2016.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. Neural networks should be wide enough to learn disconnected decision regions. In International Conference on Machine Learning (ICML), 2018.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. arXiv preprint arXiv:2010. 13363, 2020.
Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. In International Conference on Learning Representations (ICLR), 2021.
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReL.U neural networks. Neural Networks, (08:296-330, 2018.

---

Under review as a conference paper at ICLR 2022
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning (ICLR), pp. 2847-2854. PMLR, 2017.
David Rolnick and Max Tegmark. The power of deeper networks for expressing natural functions. In International Conference on Learning Representations (ICLR), 2018.
Walter Rudin. Real and complex analysis. Tata McGraw-hill education, 2006.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In ICML, 2018.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory (COLT), pp. 1517-1539, 2016.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103-114, 2017.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLUU networks. In Conference On Learning Theory (COLT), pp. 639-649, 2018
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations (ICLR), 2017.
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
PROOF PROPOSITION 2
Proof. We start with the proof of (1). is clear that Pt followed by linear isomorphism E R. with
dim(U) < ny can be implemented by + W1z + b, with some W1 E m bj E Rm.. As M is compact and hence bounded, one can further arrange b1 in a way that Wix+b1 2 holds (component wise) for every E M, which implies that ReLU i b1) = Wix + bi for all E M. Thus g(x) = ReLU((W, + b1) maps bijectively to Mi == ReLU,W, M + b1) C R. Now, uniform approximation of given continuous function f from .M to R amounts to uniform approximation of continuous function from M, to IR. By Tictze's Extension Theorem (Rudin) 2006)
we can apply Theorem from Hanin & Sellke (2017) which yields arbitrary accurate uniform approximation of continuous function on rectangular domains in R by network functions in NeRLL (m 1).
To show (2), let W1 E x and bj E R such that y, = Wiæ; b1.j= 1..j11.... m, are distinct points Mi .,,,.., Dm C [0, oo). It is then clear that also (ar) = ReI.U(Wiæ b1) maps M Mi- Now, for some function f: M + (which is automatically continuous as M is finite) we have to find a network function Fi NN (2) such that Fi (gz) = =(xx) for 1,... m. To this end,
we observe that the mapping Y/ + j =, I...., m can be interpolated by max-min string, see Hanin & Sellke (017 Definition 1) for definition, so that Hanin Selike (2017) Proposition 2) yields the desired Fi. Alternatively, one could follow the proof of Hardt & Ma (2017) Theorem 3.2.). observing that on the non-negative yj-
1....,,, m. the residual RcLU network function
constructed in the latter can be written as a ReLU network function in the sense of this work with
width two in our case. Finally, we have that Fi o Fo E NN N.. (2) and P(x;) = f(x,) for all
j ...y
PROOF PROPOSITION 4
Proof. It is clear that the existence of inner points in F(M) requires that every weight matrix of F square and full rank. Indeed, otherwise the range of is reduced a manifold of dimension less than equal to no 1 after layer that violates this condition. From then the range remains without inner points. If L = 1, then we are done, since in this case F reduces to an isomorphism on Re Otherwise, let Mj =- Aj (M) for
..., L and Mo == M. Hence F(M) Mr,. Since W. is non-singular, ur. E M, is an inner point of Mr, if and only if ur. WI for some unique point "L-1 E M This implies that component wise W 0 and further, by the fact that WL-1 is non singula,,,, 4 W + b for some unique point u E M The exact same reasoning can now iteratively be applied down the first layer. This gives a sequence of My E jj. j = 1, ..., I. so that component wise ú2 > O holds for every j. Hence, " W by for jorj=1, = 1,.., ..., L. Thus, for the inverse image B = F-! (F(M))) C M the mapping F reduces to an bijective linear affine mapping.
13

---

Under review as a conference paper at ICLR 2022
NUMERICAL EXPERIMENT
Eogerdcdelian lagal Lest Abc
Lapsr
Layer Sagerabes
0.7
010
11.
3.
010
1.x
0.2
0.
Laper dntatiens
BAL Layer
Lyger aetestoos BeC Lew Aio.
04..0
3.4
0.10
0.75
0.4
0.2
08830.8220 02900 www.00000...... 1200 120011001100000 1549 375
BT 0J
60
0.
6.0
0.1
0.4
114
PM
(a) 6 border balls center ball radius: 0.01 MSE: 0.0 UUAC: 0.0
Layer defectioe. Linerr Layer
Luyor dotailoon BAL Layes
Laaer dnfivil bowe Lager itc
1.0
0.
4
0.4
0.0
0.3
0.
-1.
01
02
60
06 87 IE D1
-30
-0.3
85
0.0
02
01
06
AF
1.
13
Layer difiilio Lageritu
Capar deteation T4t17 Lapee Mb..
0.55
0.53
11
2
0.75
0.32
0.42
(b) 6 border balls center ball radius: 0.05 MSE: 0.00026 UUAC: 0.99092
Figure 2: Additional results for Fig. 1 of the main paper. Different input datasets (a) and (b) together with the resulting transformations by each activation function and each layer learned by the neural network after 500 epochs. We also report the final decision regions, the mean-square error (MSE) and the universal uniform approximation condition (UUAC). When the conditions of Theorem 2 are fulfilled (a), the learned transformations are similar to the construction in the proof of Theorem 2. When the condition of Theorem violated (b), the intermediate layers also violate the construction in the proof. The title of each subplot describes the function which is applied to the data of the previous subplot to form the data the current subplot.
14


Reviews:
[{"review_id": "sRTjqpc7ivr", "reviewer": "Reviewer_PCRn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reviewer finds the topic studied in the paper very interesting. Expressivity bounds have been studied to understand benefits of depth. However, the case of width is also interesting and appears to be less studied in the literature. The basic fact here is that universal approximation is impossible if the width of a network is severely restricted to be less than the input dimension $n_0$. Given this, I find the question studied in this work well-motivated and natural.\n\nThe only concern with the present work is the novelty. Even though it is technical, its main message is not too strong. The reviewer does not follow how their \"results give theoretical insights on the kind of feature extraction earlier layers need to implement in order to allow the later layers to solve a givem machine learning task\", as they state in Section 2. Moreover, the reviewer thinks that the paper has an overall nice collection of (relatively) small results, but none of them is particularly strong. The maximum principle derived is perhaps the most interesting; however, it seems incremental given the Beise et al. (2021) studying the decision regions of narrow deep NNs and Johnson (2018). The other two contributions about width-restricted ReLU nets of depth 4 and cosine nets of depth 3 are nice but not in par with an ICLR paper.\n\n", "summary_of_the_paper": "The paper studies the question of expressivity of neural networks that have restricted width. Specifically, the main question is \"what happens when the maximum (among all layers) width is less or equal to the input dimension?\" \n\nFrom prior works, it is known that such width-restricted networks cannot possibly express all continuous functions on arbitrary compact sets. So the next natural question is what kind of functions/subsets M of R^n are amenable to approximation via such networks?\n\nThe main contribution is the derivation of certain topological conditions on compact sets M in R^{input dimension} that allow or exclude universal approximation by such networks. \n\nFirst, the authors derive a maximum principle stated as Theorem 1: If M is a compact subset of R^{input dimension}, then a neural network of width at most the input dimension, equipped with any continuous monotonic activation function  will necessarily attain its maximum value on the boundary of M. As a consequence, the authors show how previous lower bounds on width (w\\ge n_0 +1) are tight by providing several tight examples.\n\nSecond, the authors investigate the case where the domain consists of two disjoint compact sets and the goal is to approximate functions that take constant values on each of these sets. They give a sufficient condition under which shallow ReLU nets of width $w=n_0$ (the input dimension) and depth 4 can expreess them.\n\nThird, they also consider some expressivity properties of simple networks with cosine activations that have width only 1 and depth 3.\n\n", "summary_of_the_review": "Nice motivation about the question, but the results presented are relatively weak. There is not a \"main\" message of the paper that is in par with ICLR standards.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hum-a5z8Av", "reviewer": "Reviewer_99iL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths :\n\nThe narrow network regime is not as well studied and is a useful pursuit to obtain a complete characterization of NNs and this paper definitely takes some steps in that direction. \n\nSection 3, which describes the maximum principle is interesting as it talks about the existence of compact subsets that cannot have an universal approximation guarantee when the activation functions are monotonic and continuous, even if you consider classes of NNs with arbitrary depth!\n\nSection 4, talks about subsets that can guarantee exact interpolation and universal approximation guarantees. They specifically consider subsets that are disjoint union of a finite number of compact sets and functions that are constant in each disjoint piece. This can be considered a large class of functions that are used for clustering/classification applications. They provide some sufficient conditions that these sets need to satisfy in order for exact interpolation by a constant depth ReLU network (for two compact sets and for more than two, there exists some depth (input dependent) that can give exact interpolation.\n\nFinally, they show that an arbitrary finite sample set can be exactly interpolated by a constant width and depth network that has a cosine activation function.\n\nWeaknesses:\n\nTheoretical:\n\nMy main issues is about the approximable subsets. The authors consider studying functions that are constant over disjoint compact sets, akin to clustering/classification type applications. They present results that target exact interpolation in Theorem 2 and Corollary 2. Now can the assumptions on mutual locations be removed if targeting universal approximation and allowing the depth to be arbitrarily large ? Or is it that in this case exact interpolation is as hard as universal approximation? \n\nIn addition, I was wondering about the applicability of theorems in Sections 3 and 4 with a cosine activation function which is not a monotonic function, but does well on an arbitrary finite set (Theorem 3)? It would be nice to have a discussion to consider the applicability of non-monotonic activations as well.\n\nAs a general comment, when using NN($n_0$) to represent the class of functions, if possible it would be useful to mention the depth (which may be input dependent) to understand the dependence on the depth which is able to approximate/interpolate the target functions.\n\n\nPresentation and minor issues:\n\nAnother issue is about the presentation of results. I think the paper would be much better with illustrations of sets that help reader visualize the geometry, as these sets are interesting examples/counter-examples. \n\nMinor suggestions:\n1) In the Introduction ...\"An important results states that a width larger..\", is stated without mentioning where the result appeared (which is mentioned in the next section though).\n2) In  page 4, when the authors mean $\\sigma$ is partially constant, do they mean piecewise monotonic? It would be nice to have the statements of all the auxiliary theorems and lemmas that are not common to be in the appendix for easy reference.", "summary_of_the_paper": "The paper focuses on approximation of NNs in the narrow regime, i.e, when the width of the network less than the input dimension ($n_0$) and asks the question:\nWhat compact subsets M of $R^{n_0}$ still allow universal approximation or exact interpolation for all functions that map from M to R.?\n\nIt first shows the existence of compact subsets that do not allow for such universal approximation guarantee.\n\nThen the paper presents sufficient conditions on certain compact subsets so that some universal approximation/exact interpolation guarantee can be attained and these results are targeted for clustering/classification applications. The functions here are piecewise-constant on disjoint compact sets.\n\nThe assumptions on the activation functions are general which includes most of the commonly used ones in practice as well.", "summary_of_the_review": "I think the problem is definitely interesting, to understand the limitations of narrow networks and of course the extent of positive results that can be extracted from it. I think this work takes some steps in that direction, but definitely requires a bit more investigation (as specified above) and also the presentation could be made better with some illustrations/visualization of the sets in the main results, which may help communicate the ideas in a better way.\n", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "bxjva6snFKX", "reviewer": "Reviewer_oqnR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "# Major observations\n\nIn Section 4, repeating what I said above, the authors claim through Theorem 2 a result applicable to a \"finite collection of disjoint n0-dimensional compact sets\" However, except for Corollary 2, which is not explicitly linked to Theorem 2, the entire discussion for the second contribution focuses on only 2 sets. Hence, in Section 6, it is not clear how they claim to be validating the result by using domains consisting of more than 2 disjoint sets.\n\nIn Theorem 2, do the authors really mean $K_2 \\subset \\mathbb{R}^{n_0} \\setminus \\overline{S}$ instead of $K_2 \\subset \\mathbb{R}^{n_0} \\setminus S$? \n\n# Minor observations\n\n1) Introducion\n\n\", we refer to (DeVore et al., 2020) for an overview on recent developments\": use semicolon (;)\n\n\"‖·‖is the Euclidean norm\": do not start a sentence with something other than a word\n\n\"j-te coordinate axis\": j-th\n\nI can follow your notation, but I strongly encourage you to describe what L is at the begining instead of at the end, at which point you have already used it to define a number of other things.\n\nAdditional references:\n- On the discussion of expressiveness in terms of depth and width: [1] (figure 5)\n- On the ability of memorization in terms of expressiveness: [2] (figure 5, left)\n\n2) Related work\n\nThe meaning of $C$ and $L_p$ is never mentioned; neither what exactly each term is in the notation that you start using here. For example, that the first term in the tuple is the domain and the second is the image encompassing the family of functions.\n\n\"multiply pairwise compact components\": multiple\n\n3) Maximum principle\n\nRemind the reader what \"NNσ(n0)\" stands for.\n\n\"on arbitrary compact sets is impossible:\": does not seem to be the right place to use a comma\n\nBriefly repeating the meaning of technical terms can make wonders to accessibility.\nIn Theorem 1, I would recommend expaning the statement as \"takes its maximum value *at the boundary* ∂M\".\n\n\"to network function of width larger than the input dimensions\": confusing; please rewrite\n\n\"straight forward\": straightforward \n\n\"In Theorem 1 show that\": Theorem 1 shows that\n\n4) Approximation properties on subsets\n\n\"on such kind of sets\": that seems to imply whether it applies to each set individually; perhaps something like \"on such domains\" would be better here\n\n7) Conclusion\n\n\"haven shown\": have shown\n\n\"with cos as activation function\": with cosine as activation function\n\nA) Appendix\n\nProof of Corollary 2: what do you mean by \"Proposition 1.2\"?\n\n# References cited\n\n[1] https://arxiv.org/abs/1711.02114\n\n[2] https://arxiv.org/abs/1906.00904", "summary_of_the_paper": "This paper presents three results concerning the universal approximation of functions on compact sets under a width regime for which universal approximation in general is not possible. The authors make a convincing case that this represents an important frontier both for applications and for a better understanding of what neural networks can represent. While I appreciate the first result, I am confused with the second and I do not think the third is relevant.\n\nThese results are the following:\n\n1) The maximum principle\n\nThis is an interesting observation about the maximum (and minimum) value achieved by neural network with continuous monotonic activation and width bounded by the input layer on a compact domain is always at the boundary of such domain. Trying to break their result made me understand and agree with their claim that this could be understood as a \"root cause why universal approximation with functions from NNσ(n0) on arbitrary compact sets is impossible\".\n\n2) The result on disjoint domains\n\nIn Section 4, the authors claim through Theorem 2 a result applicable to a \"finite collection of disjoint n0-dimensional compact sets\". Notably, most of their work there focuses on exact representation, which reflects the fact that they are considering functions that are constant on each disjoint set. We can reasonably associate that to classification tasks, but then we cannot assume any probabilistic meaning with something like a softmax layer.\n\n3) The result on harmonic activations\n\nThe authors shows that universal approximation can be achieved on a finite and discrete domain with the composition of cosine functions. This result lies entirely on the domain being discrete and finite, which actually breaks any dependence to the width of the input layer. For that reason, I do not think that it is that relevant because it has nothing to do with the main theme of the paper.", "summary_of_the_review": "In full disclosure, I am curious to know what the other reviewers think of the first contribution, but at this point this is the most positive part of the paper in my view.\n\nHowever, the organization and discussion of the second contribution really confuses me. I am not comfortable with the current organization of the results related to Theorem 2 and the corresponding experiments in Section 6.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Kbnf2Y1MN_", "reviewer": "Reviewer_qHTG", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The manuscript has three main contributions: (1) A maximum principle when the activation function is continuous and monotonic (such as ReLU), showing that the neural networks must be at least n_0 + 1 wide, (2) An interesting condition on two compact sets (one of them being contained in a cone-like sector that doesn’t intersect with the other) that is sufficient to allow exact fits of piecewise constant functions, and (3) A width 1 and depth 3 neural network with cosine activation is a universal approximator for a finite sample set. \n\nStrengths: \n - The paper is well written and easy to follow. The discussion regarding prior work is quite clear and extensive.\n - The authors are investigating an unusual question by restricting the types of compact sets to prove universal approximation theorems. Therefore, I think the manuscript has significant merit in the way that it is investigating universal approximation theorems. \n-  I agree with the authors that universal approximation on certain subsets is often what is needed in practice. \n\nWeakness:  \n - Some of the theoretical results only apply to monotonic activation functions, which covers many important activation functions, but certainly not as general as related recent papers on deep narrow neural networks.  ", "summary_of_the_paper": "In the mathematical theory of neural networks, universal approximation theorems typically establish the density of a class of neural networks within a certain function space. In recent years, it has been shown that a width larger than the input dimension is needed to allow universal approximation theorems for continuous function spaces defined on arbitrary compact sets.  In this paper, the authors investigate what kind of subsets of R^n allow for a universal approximation theory with neural networks that have a width <= input dimension. \n\n", "summary_of_the_review": "In my opinion, the article is asking an interesting question by restricting to certain compact sets. I believe that the manuscript is making a reasonable theoretical contribution to the analysis of deep narrow neural networks.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* Study expressive power of narrow networks. 

*Strengths:*
- Study the narrow setting, which is not as well studied as the wide setting. 
- Some reviewers found the paper well written. 

*Weaknesses:*
- Restricted class of targets and activations. 
- Similar results have appeared in previous works. 

*Discussion:* 

99iL asked about the possibility to remove certain assumptions and the extension to other activations. Authors answer negatively to both. 99iL acknowledges the response and concludes the so-called maximum principle is the most interesting result, but also points out that similar results appear in previous work and that it would have been good to see some extensions. qHTG indicates that the paper is well written and has interesting contributions but that some of the theoretical results only apply in settings that are more restrictive than in other recent related works. Authors agree that generalizations deserve to be investigated in the context of the presented results, but point out that their principle does not apply in that case, and hence that such generalizations are out of scope. Although qHTG identifies several good aspects in this work, they maintain the overall assessment of just marginally above the threshold. PCRn finds the work very interesting but is concerned about the novelty and points out that although the work is technical, the main message is not very strong and that the extraction of insights to solve tasks is not as clear. PCRn concludes that the paper presents various relatively weak results but not a sufficiently significant message. Authors remark that some of their results constitute a mathematical tool for future works. 

*Conclusion:* 

One reviewer rated this work marginally below the acceptance threshold and three other marginally above. Considering the reviews and the discussion, I conclude that this paper obtains a few interesting results but leaves much for future work. Further development of the current results would make the article significantly stronger. In view of the very high quality of other submissions to the conference, I find that this article tightly misses the bar for acceptance. Therefore I recommend to reject this article. I encourage the authors to revise and resubmit.
Decision: Reject