Year: 2021

Abstract:
The understanding about the minimum width of deep neural networks needed to ensure universal approximation for different activation functions has progressively been extended (Park et al., 2021). 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.

heading: 1 INTRODUCTION
text: 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, or 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 Lp norms) by neural network functions that have only one hidden layer for nearly every activation function (Cybenko, 1989; Hornik, 1991). In 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, 2018; Yarotsky, 2017; 2018), or by investigating the number off piece-wise linear regions (Montufar et al., 2014; Serra et al., 2018; Hanin & Rolnick, 2019); we refer to (DeVore et al., 2020) for an overview on recent developments. Since empirical observations showed that depth has a 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 et al., 2014; Raghu et al., 2017; Rolnick & Tegmark, 2018; Lin et al., 2017; Cohen et al., 2016). Besides this, the role of width in 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 a width larger than the input dimension is needed to 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., 2021).
In a further line of research, the capabilities of neural networks to memorize finite sample sets is investigated (Yun et al., 2019; Vershynin, 2020; Bubeck et al., 2020; 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 ⊂ Rn admit universal approximation by neural network functions with a maximum layer width less than or equal to the input dimension, i.e. network functions that violate the necessary condition for universal approximation given in Hanin (2019) and Park et al. (2021) for arbitrary compact sets.
Let us introduce the following notation: For a set D ⊂ Rn we denote by D◦ the set of interior points, by D its closure and by ∂D = D \D◦ the boundary of D. By ‖·‖ we mean the Euclidean norm. For a linear subspace U ⊂ Rn, we denote by dim(U) its dimension and by PU : Rn → U the orthogonal linear projection on U . We denote by ej the unit vector of the j-th coordinate axis in Rn. For some v ∈ Rn and j ∈ {1, ..., n}, we write v(j) for the j−th component of v. For some depth L ∈ N, we consider neural network functions of some , F : Rn0 → RnL where n0 is called the input dimension and nL the output dimension. Our network functions have the following form F :=WL(AL−1 ◦ ... ◦A1) + bL (1) where Aj(x) = σ(Wjx+ bj) with Wj ∈ Rnj×nj−1 (weights), bj ∈ Rnj (bias), where j = 1, ..., L, and σ : R → R the activation function. The application of σ and the inverse image σ−1 are understood to be applied element wise to vectors or subsets of Rn. The widely used activation function rectified linear unit, shortly ReLU, is defined by t 7→ max{t, 0}. As a shorthand notation of the function implemented by the first k layers of a network function, we set
Fk =Wk (Ak−1 ◦ ... ◦A1) + bk, (2)
for k ∈ {1, ..., L−1}. We call nj the width of layer j = 1, ..., L. The width of the network is defined as ω(F ) = max{nj : j = 1, ..., L} and L is called the depth of the network. For m,L ∈ N and an activation function σ, NN kσ(m,L) is the set of network functions F : Rn0 → Rk of the form (1) with activation σ and of maximum width m, i.e. ω(F ) ≤ m, and depth L, i.e. L layers including the final linear layer. In case that Rk = R we omit the latter and write NN σ(m,L) instead, and in case the the depth is not specified, meaning that arbitrary depth is allowed, we write NN kσ(m), NN σ(m), respectively. We say that a compact subset M ⊂ Rn0 admits universal uniform approximation of functions in some function class of mappings from M to R by network function of NN σ(m,L) or NN σ(m), if for every f :M → R in that class and every ε > 0, there exists some F ∈ NN σ(m,L), respectively F ∈ NN σ(m), such that
max x∈M |f(x)− F (x)| < ε. (3)

heading: 2 RELATED WORK
text: 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.e. the minimum number of neurons per layers, here denoted by ωmin, needed for universal approximation in C(M,RnL), i.e. the space of continuous functions from a compact set M to RnL endowed with the norm of uniform convergence, and Lp(M,RnL) with some set M ⊂ Rn0 , i.e. the space of functions f = (f1, ..., fnL) from M to RnL such that every |fj |p is integrable over M , endowed with the usual Lp norm. Since in this work we are interested in universal approximation in C(M,R), we refer to Lu et al. (2017), Kidger & Lyons (2020) and Park et al. (2021) for the case of Lp approximation. For the case of C(M,RnL), it was proven in Hanin & Sellke (2017) that
n0 + 1 ≤ ωmin ≤ n0 + nL, for ReLU activation, (4)
which has been tightened in Park et al. (2021) to
ωmin ≥ max{n0 + 1, nL} for ReLU and STEP activation, (5)
where STEP refers to the threshold activation that maps to 1 on {x ≥ 0} and 0 otherwise. It has been shown at the same time in Johnson (2018) and Beise et al. (2021) that
ωmin ≥ n0 + 1 for ReLU + injective continuous activation. (6)
The activation functions allowed in Johnson (2018) 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 R. 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; Vershynin, 2020; Bubeck et al., 2020; Park et al., 2020).
In this work, we only consider width less than or equal to n0 and investigate uniform approximation on certain compacts subsets of the input space. According to the above result (6), we cannot expect universal approximation for all compact M ⊂ Rn0 . However, a common assumption in applications is that approximation is only needed on a certain subset. We derive some topological conditions on M that allow or exclude a kind of universal approximation under these circumstances. Although narrow neural networks, as they are considered in this work, are not common in practical applications, many networks exhibit a 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 to solve a given machine learning task. Our main contributions are as follows:
1. A maximum principle is given for F ∈ NN σ(n0) with σ continuous and monotonic. This allows to conclude that the lower bound ωmin ≥ n0 + 1 in (6) is sharp for a wide range of subsets M , e.g. when M = ∂D ∪ {c} for some D with non-empty interior and c ∈ D◦.
2. We show that for the case of two disjoint compact sets, the existence of a 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 NNReLU(n0, 4). A weaker result is concluded for the case of multiple pairwise compact components.

heading: 3 MAXIMUM PRINCIPLE
text: Let us recall thatNN σ(n0) designates the set of network functions with activation function σ, having maximum width n0 and arbitrary depth. In this section, we will prove a maximum principle for network functions ofNN σ(n0) for a wide class of activation functions. This principle can be viewed as a root cause why universal approximation with functions from NN σ(n0) on arbitrary compact sets is impossible as shown in Johnson (2018) and Beise et al. (2021), see (6). This also immediately leads to a topological condition on subsets of Rn0 that do not admit universal approximation by functions in NN σ(n0). Theorem 1 (Maximum Principle). Let M be some compact subset of Rn0 and σ a continuous, monotonic activation function. Then every F ∈ NN σ(n0) takes its maximum value at the boundary ∂M .
Note that, considering −F instead of F , the latter result also implies that the minimum value is taken on ∂M . 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:
Corollary 1. Let M be some compact subset of Rn0 such that ∂D ⊂M and M ∩D◦ 6= ∅ for some non-empty open set D ⊂ Rn. Then M does not admit universal uniform approximation of continuous function by network functions from NN σ(n0).
The latter results naturally lead to the following question: Is it possible to uniformly approximate arbitrary continuous functions on the unit sphere (in Rn0) with arbitrary accuracy by network functions as they are considered in Theorem 1? Some positive approximation results are given in the next section, but a gap to an answer to the question remains.
It is not clear to us whether the conditions of Theorem 1 can be weakened in 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 : Rn0 → R be a neural network function of arbitrary width but with weight matrices having rank less than or equal to n0. Does a maximum principle similar to Theorem 1 apply in this case? The following example shows that the maximum principle in Theorem 1 does not hold in this case.
Example 1. Let M = [−1, 1] and let W1 ∈ R2×1 and b1 ∈ R2 implement the following linear affine mapping
W1x+ b1 = ( x+ 1 x ) .
Then M1 = ReLU(W1M + b1) is given by M1 =M1,1 ∪M1,2 where
M1,1 := {(x+ 1, 0)T : x ∈M, and x < 0}
M1,2 := {(x+ 1, x)T : xT ∈M, and x ≥ 0}.
Now, let v = (1, 1/2)T ∈ R2, W2 ∈ R2×2 and b2 ∈ R2 such that x 7→ W2x + b2 implements the orthogonal projection onto the hypersurface V := {x ∈ R2 : xT v = (1, 0)v}. That is, the hypersurface orthogonal to v which intersects (1, 0)T . Then both, M1,1 and M1,2 are mapped to the line M2 := {y ∈ R2 : y = (1, 0)+λ(−1/2, 1), 0 ≤ λ ≤ 1/2} and since those vectors are contained in the first quadrant we have
M2 = ReLU(W2(ReLU(W1M + b1) + b1).
It can further easily be verified that, under the latter two layer network function, 0, 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 ∈ R2 such that the linear map x 7→ W3x as a mapping from M2 to R takes its minimum or maximum value at (1, 0) only.
By concatenation of additional components to the input dimension such that M = [−1, 1]× [0, 1]d, d ∈ N, and adaptation of the weights W1,W2 and bias b1, b2 in a way that these additional components are mapped identically under the action of the two layer network function x 7→ ReLU(W2(ReLU(W1x+ b1) + b1), the above example can be extended to higher dimensions.
The following proposition provides the main observation for the proof of Theorem 1.
Proposition 1. Let M be a compact subset of Rn0 , σ a continuous, monotonic activation function and F ∈ NNn0σ (n0) such that all weight matrices Wj , j = 1, ..., L, are square and have full rank. If for some x ∈M◦ the image F (x) is a boundary point of F (M), i.e. F (x) ∈ ∂F (M), then there is an x̃ ∈ ∂M such that F (x̃) = F (x).
Proof. In case that σ is injective, the whole network function F is injective since the weight matrices are assumed to be square and of full rank. Hence, the invariance of the domain theorem gives that no x ∈ M◦ can be mapped to ∂F (M). The remaining case is that σ is partially constant. Then, given an x ∈ M◦ with F (x) ∈ ∂F (M), let k̃ be the smallest k ∈ {1, ..., L − 1} such that σ(Fk̃(x)) ∈ ∂σ(Fk̃(M)). Notice that such a k̃ must exist since, according to the invariance of the domain theorem, the last injective, linear affine mapping x 7→ WLx cannot map inner points to boundary points. Then, necessarily for at least one component of Fk̃(x), a partially constant part of σ is active. More explicitly, say (Fk̃(x))
(j) ∈ [aj , bj ] ⊂ R with σ(t) = cj , where cj is the constant value taken for all t ∈ [aj , bj ], for some indices j ∈ I ⊂ {1, ..., n0}. In case that one of those intervals can be enlarged arbitrarily to either [aj ,∞) or (−∞, bj ], which would be the case for ReLU activation, we can find a t ∈ R such that xk̃ = Fk̃(x) + tej ∈ ∂Fk̃(M) and with σ(xk̃) = σ(Fk̃(x)). In a next step we show that such an xk̃ can also be found in cases where the length of the intervals [aj , bj ] are upper bounded. In those cases we may assume that the intervals [aj , bj ] are maximum in the sense that at their left and right end σ is not constant any more, and I is maximum in the sense that for every other index, the activation function σ is injective in a neighbourhood. Indeed, if such components would not exist, the component wise application of σ would be injective in a small neighbourhood of Fk̃(x) and the invariance of the domain theorem would exclude that σ(Fk̃(x)) ∈ ∂σ(Fk̃(M)). By the selection of k̃, Fk̃(x) is still an inner point of Fk̃(M). The fact that the inner point Fk̃(x) ∈ (Fk̃(M))◦ is mapped to a boundary point by the element wise application of σ implies that there is some non-empty Ĩ ⊂ I with corresponding tj ∈ R such that
tj ∈ [−(Fk̃(x)) (j) + aj ,− (Fk̃(x)) (j) + bj ], j ∈ Ĩ (7) xk̃ := Fk̃(x) + ∑ j∈Ĩ tjej ∈ ∂Fk̃(M). (8)
Indeed, otherwise,
Fk̃(x) + n0∑ j=1 tjej ∈ (Fk̃(M)) ◦
where for some small ε > 0 and all j ∈ I , tj may be chosen arbitrarily in (−(Fk̃(x))(j) + aj − ε,−(Fk̃(x))(j) + bj + ε) and ε > |tj | > 0 for j /∈ I . By the definition of I and the corresponding
intervals [aj , bj ], this would imply that σ ( Fk̃(x) ) is an inner point of σ ( Fk̃(M) ) . Now, (8) implies that there is a x̃ ∈M such that
Fk̃(x̃) = Fk̃(x) + n0∑ j=1 tjej ∈ ∂Fk̃(M),
with tj as in (7). Considering that Wk̃ is square and has full rank, the inverse image of Fk̃(x̃) under x 7→Wk̃x+ bk̃ is a boundary point of σ(Fk̃−1(M)) in case that k̃ > 1 and a boundary point of M in case when k̃ = 1. In the last case we are done. In the first case, the same reasoning can be applied to x̃ instead of x, and the iterative application finally leads to a boundary point of M that is mapped to σ ( Fk̃(x̃) ) = σ ( Fk̃(x) ) and hence follows the same trajectory when passed through the last layers from k̃ to L.
Proof. (Theorem 1) We may assume that M◦ is non-empty and that every weight matrix Wj , j = 1, ..., L− 1, is square and of full rank. Otherwise the result is trivial, because F (M) = ∂F (M). Hence the assumption of Proposition 1 holds for F̃ = AL−1 ◦ ... ◦A1. Since the linear mapping x 7→ WLx from RnL−1 to R takes its maximum and minimum values on ∂F̃ (M), the latter proposition also implies that F takes its maximum value on ∂M .

heading: 4 APPROXIMATION PROPERTIES ON SUBSETS
text: In this section we give some approximation results that show that, despite the limitations induced by Theorem 1, the network functions considered in this work still allow some weaker kind of universal approximation on subsets. The first result in this section follows from existing results on approximation by network functions. The first point can be deduced from Hanin & Sellke (2017, Theorem 1). The second point can be derived from Hanin & Sellke (2017, Proposition 2) or from Hardt & Ma (2017, proof of Theorem 3.2.).
Proposition 2.
1. Let M be some compact subset of Rn0 . If there exists a subspace U ⊂ Rn0 with dim(U) < n0 such that PU is injective as a mapping from M to U , then M admits universal uniform approximation of continuous function by network functions in NNReLU(dim(U) + 1).
2. Let M = {x1, ..., xm} ⊂ Rn0 be a finite set and f : M → R some mapping. Then there exists a network function F ∈ NNReLU(2) such that F (x) = f(x) for all x ∈M .
The proof is almost straightforward, given the results from the aforementioned works. A proof can be found in the appendix.
We next extend the second statement of the latter proposition to the case of two disjoint n0-dimensional compact sets.Theorem 1 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 in classification tasks where each point in a particular disjoint compact set belongs to the same class, i.e. these sets constitute different disjoint clusters of the data.
Theorem 2. Let M = K1 ∪ K2, with disjoint compact sets K1,K2 ⊂ Rn0 such that for some c ∈ Rn0 and some linearly independent v1, ..., vn0 ∈ Rn0 the set K1 is contained in the sector
S := {x ∈ Rn0 : x = c+ n0∑ j=1 λjvj , λj > 0}
and K2 ⊂ Rn0 \ S. Then for every function f :M → R that takes constant values on K1 and K2, respectively, there exists a network function F ∈ NNReLU(n0, 4) such that
f(x) = F (x)
for every x ∈M .
The conditions of Theorem 2 are verified and inspected by numerical experiments in Section 6. However, 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 1 is clear that K2 cannot completely enclose K1 when the maximum width is upper bounded by n0, 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 Rn0 that are strictly separable by a linear hyper surface. Then there exists an F ∈ NNn0ReLU(n0, 2) such that F (K) is a single vector in Rn0 \M and F (x) = x for all x ∈M . Moreover, F can be arranged in a way that given ε > 0
min x∈K ‖F (K)− x‖ < ε.
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 = ⋃d j=1Kj with pairwise disjoint compact sets Kj ⊂ Rn0 , j = 1, ..., d such that for every Kj there exist vj ∈ Rn0 and qj ∈ R such that vTj x > qj for all x ∈ Kj , and vTj x < qj for all x ∈M \Kj , i.e. there are linear hypersurfaces separating each Kj from the remaining Kl, l 6= j. Then for every function f : M → R that takes constant values on every Kj , j = 1, ..., d, there exists a network function F ∈ NNReLU(n0) with
f(x) = F (x)
for every x ∈M .
Proof. (Corollary 2) By means of Proposition 3, we find an F1 ∈ NNn0ReLU(n0) such that F1(x) = x for x ∈ ⋃d j=2Kj and a1 := F1(K1) is a single vector in Rn0 \ ⋃d j=2Kj . Proposition 3 also allows us to choose F1 in a way that a1 is sufficiently close to K1 that the conditions of Corollary 2 still apply to ⋃d j=2Kj ∪ {a1}. We can iteratively apply Proposition 3 to find F1, ..., Fd ∈ NN n0 ReLU(n0) such that Fd ◦ ... ◦ F1(Kj) = aj , j = 1, ..., d for pairwise distinct a1, ..., ad ∈ Rn0 . Now, for a given f :M → R with f(x) = yj for all x ∈ Kj , j = 1, ..., d, Proposition 2 yields an F̃ ∈ NNReLU(2) with F̃ (aj) = yj for all j = 1, ..., d. The desired network function is then obtained by F := F̃ ◦ Fd ◦ ... ◦ F1.
Proof. (Proposition 3) Let us remind that e1, ..., en0 are the standard basis vectors in Rn0 . By assumption, there is a v ∈ Rn0 , with ‖v‖ = 1 and a q ∈ R such that vTx > q for x ∈ K and vTx < q for x ∈M . For a given ε > 0 we may assume that the linear hyper surface defined by v, q, H := {x ∈ Rn0 : vTx = q} is so near to K that for some a ∈ K that realizes the minimum distance of K to H we have vTa = q + ε/2. (9) Indeed, otherwise we can shift the hyper surface accordingly by increasing q. Then, by the fact that ‖v‖ = 1, (9) means that a has a distance equal to ε/2 to H and ã := a− ε/2 v ∈ H is the unique vector in H that realizes this distance. Let V1 ∈ Rn0×n0 such that x 7→ V1x implements a length preserving rotation that maps v to −e1. Then x 7→ V1x − V1ã maps H to span(e2, ..., en0) and K1 := V1K − V1ã is contained in the half space of vectors with negative first component and with a1 := V1a− V1ã = −ε/2 e1, and M1 := V1M − V1ã is contained in the half space of vectors with positive first component. By compactness ofK1 and M1, we can find u1, ..., un0 ∈ span(e2, ..., en0), such that for a δ > 0, −u1 − δe1, ...,−un0 − δe1 are linearly independent and such that with δ sufficiently small
K1 ⊂ S− := {x ∈ Rn0 : x = n0∑ j=1 λj(−uj − δe1), λj > 0}
M1 ⊂ S+ := {x ∈ Rn0 : x = n0∑ j=1 λj(uj + δe1), λj > 0}.
Let V2 ∈ Rn0×n0 such that x 7→ V2x maps −uj − δe1 to −ej for j = 1, ..., n0. Then, by linearity, every uj + δe1 is mapped to ej for j = 1, ..., n0. 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 V2K1 to 0 and maps V2M1 identically. We can now apply the inverse of the linear affine mappings which will map V2M1 back to M , i.e. for
F (x) := V −11 V −1 2 ReLU(V2(V1x− V1ã)) + ã.
With this F we have F (M) =M and F (K) = F (a) = ã. Note that by (9) and the definition of ã min x∈K ‖x− F (a)‖ = ε/2 < ε
which concludes the proof.
Proof. (Theorem 2) Let V be the matrix that results from the concatenation of the columns v1, ..., vn0 and set W1 := −V −1 and b1 := W1(−c). Then the mapping x 7→ W1x maps the vj to −ej , j = 1, ..., n0 and W1K1 + b1 is a subset of
S− := {x ∈ Rn0 : x = n0∑ j=1 λj(−ej), λj > 0}
and W1K2 + b1 ⊂ Rn0 \ S−. Thus, the one layer network function F1(x) := ReLU(W1x + b1) maps all x ∈ K1 to 0 and x ∈ K2 are mapped to
{x ∈ Rn0 : x = n0∑ j=1 λjej , λj ≥ 0} \ {0}.
Hence, with a sufficiently small q > 0, F1(K1) and F1(K2) are strictly separated by the linear hyper surface {x ∈ Rn0 : (1, 1, ...., 1)x = q}. The twofold application of Proposition 3 yields two network functions that can be concatenated to a three layer network function F2 ∈ NNn0ReLU(n0, 3) with F2(x) = W4 ReLU(W3 ReLU(W2x + b2) + b3) + b4 and such that F2(F1(K1)) and F2(F1(K2)) are two distinct vectors u1, u2 in Rn0 , respectively. For a given f : M → R that takes constant values on K1 and K2, say a1, a2 ∈ R, respectively, we attach a linear affine layer x 7→ wTx + b5, where w ∈ Rn0 , b5 ∈ R such that wTu1 + b5 = a1 and wTu2 + b5 = a2. This mapping is integrated in the final layer of F2 ◦ F1 and finally gives
F (x) = wTW4 ReLU(W3 ReLU(W2 ReLU(W1x+ b1) + b2) + b3) + w T b4 + b5.
We conclude this section with a comment on implications of our results on generalisation. In Zhang et 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 2, Theorem 2 and Corollary 3 we show that network functions of width less than or equal than to input dimension in many configurations also implement an exact fit of the training data. At the same time these network functions are restricted by the maximum principle given in Theorem 1, which may contradict the underlying distribution of the data at hand.

heading: 5 UNIQUENESS
text: A maximum principle similar to Theorem 1 also applies for harmonic and holomorphic functions, that is, the null space of the Laplace operator and the null space of ∂z := 1/2(∂x + i∂y) (x real part, y imaginary part), respectively (Rudin, 2006). As a consequence, a uniqueness theorem applies which states that two harmonic, respectively holomorphic, functions coincide on the interior of a given set when they coincide on its boundary, respectively. In view of Theorem 1, it is hence natural to ask whether a similar result applies in the case of network functions in NN σ(n0). However, the proof for the case of harmonic and holomorphic functions relies on the fact that these functions form a vector space, which is not the case for the set NN σ(n0). The following examples show that a uniqueness theorem does not hold, in general, for the network functions with (strictly) monotonic activation functions considered in this work.
Example 2. Let σα(x) be the leaky ReLU function defined by σα(x) = x for x ≥ 0 and σα(x) = αx for x < 0 with α > 0. Then
x 7→ σα ( 1
(1 + α) σα(x) +
α
(1 + α)
) and x 7→ σα( 1
2 σα(x+ 1))
both map −1 to 0 and 1 to 1, but the first one maps 0 to α/(1 + α), 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 σ be the sigmoid function. For x 7→ σ(ax+ b), one can arrange a > 0, and b ∈ R, such that in one case only a concave and in a second case a convex excerpt of sigmoid is active for x in [0,1], respectively, and such that both functions coincide at 0 and 1. 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. Proposition 4. Let M be a compact subset of Rn0 , F ∈ NNn0ReLU(n0) and B = F−1 ((F (M))◦) the inverse image of the inner points of F (M). Then F is linear affine and bijective as a mapping from B to (F (M))◦.
A proof of Proposition 4 is given in the appendix. As a consequence we have. Corollary 3. Let F,G ∈ NNn0ReLU(n0) and M ⊂ Rn0 be some compact set. If F and G coincide on a set of vectors v1, ..., vn0+1 in
K := F−1 ((F (M))◦) ∩G−1 ((G(M))◦) ,
such that vj − vn0+1, j = 1, ..., n0 are linearly independent, then F (x) = G(x) for all x ∈ K.
It 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 Rn0 .

heading: 6 NUMERICAL EXPERIMENT
text: 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 a center ball of a different class. The border balls use a radius of 0.125 and a 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 2, 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 are of the form F ∈ NNReLU(2). We used a 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-squared error (MSE) as our cost function. The different datasets and results are reported in Fig. 1. We rate an experiment as successful when the universal uniform approximation condition (3) tends to zero. It can be observed in Fig. 1 (a) that, when the conditions of Theorem 2 are fulfilled, the neural network can approximate the function correctly and the different layers are learning transformations similar to the constructions in the proof. When the conditions are violated, as is shown in Fig. 1 (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 in Fig. 2 in the appendix.

heading: 7 CONCLUSION
text: We identified a maximum principle that holds in the case of width less than or equal to 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
that, although being not sufficient for universal approximation in the general sense, ReLU network functions of width less than or 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 a 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.

heading: REPRODUCIBILITY STATEMENT
text: This paper is a contribution to the theory of neural networks, which includes some numerical examples to 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.

heading: A APPENDIX

heading: PROOF PROPOSITION 2
text: Proof. We start with the proof of (1). It is clear that PU followed by a linear isomorphism E : U → Rm with m = dim(U) < n0 can be implemented by x 7→ W1x + b1 with some W1 ∈ Rm×n0 , b1 ∈ Rm. AsM is compact and hence bounded, one can further arrange b1 in a way thatW1x+b1 ≥ 0 holds (component wise) for every x ∈M , which implies that ReLU(W1x+ b1) =W1x+ b1 for all x ∈M . Thus g(x) = ReLU(W1x+ b1) maps M bijectively to M1 := ReLU(W1M + b1) ⊂ Rm. Now, uniform approximation of a given continuous function f from M to R amounts to uniform approximation of continuous function from M1 to R. By Tietze’s Extension Theorem (Rudin, 2006) we can apply Theorem 1 from Hanin & Sellke (2017) which yields arbitrary accurate uniform approximation of continuous function on rectangular domains in Rm by network functions in NNReLU(m+ 1). To show (2), let W1 ∈ R1×n0 and b1 ∈ R such that yj =W1xj + b1, j = 1, ...,m, are distinct points M1 = {y1, ..., ym} ⊂ [0,∞). It is then clear that also F0(x) := ReLU(W1x+ b1) maps M to M1. Now, for some function f :M → R (which is automatically continuous as M is finite) we have to find a network function F1 ∈ NNReLU(2) such that F1(yj) = f(xj) for j = 1, ...,m. To this end, we observe that the mapping yj 7→ f(xj) j = 1, ...,m can be interpolated by a max-min string, see Hanin & Sellke (2017, Definition 1) for a definition, so that Hanin & Sellke (2017, Proposition 2) yields the desired F1. Alternatively, one could follow the proof of Hardt & Ma (2017, Theorem 3.2.), observing that on the non-negative yj , j = 1, ...,m, the residual ReLU 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 F = F1 ◦ F0 ∈ NNReLU(2) and F (xj) = f(xj) for all j = 1, ...,m.

heading: PROOF PROPOSITION 4
text: Proof. It is clear that the existence of inner points in F (M) requires that every weight matrix of F is square and of full rank. Indeed, otherwise the range of M is reduced to a manifold of dimension less than or equal to n0 − 1 after a layer that violates this condition. From then on the range remains without inner points. If L = 1, then we are done, since in this case F reduces to an isomorphism on Rn0 . Otherwise, let Mj := Aj(Mj−1) for j = 1, ..., L and M0 := M . Hence F (M) = ML. Since WL is non-singular, uL ∈ML is an inner point of ML if and only if uL =WLuL−1 for some unique point uL−1 ∈ M◦L−1. This implies that component wise uL−1 > 0 and further, by the fact that WL−1 is non-singular, uL−1 =WL−1uL−2 + bL−1 for some unique point uL−1 ∈M◦L−2. The exact same reasoning can now iteratively be applied down to the first layer. This gives a sequence of uj ∈M◦j , j = 1, ..., L so that component wise uj > 0 holds for every j. Hence, uj =Wjuj−1 + bj for j = 1, ..., L. Thus, for the inverse image B = F−1 (F (M)◦) ⊂M◦, the mapping F reduces to an bijective linear affine mapping.

heading: NUMERICAL EXPERIMENT

Review summaries:
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.  These results are the following:  1) The maximum principle  This 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".  2) The result on disjoint domains  In 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.  3) The result on harmonic activations  The 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.

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: What compact subsets M of $R^{n_0}$ still allow universal approximation or exact interpolation for all functions that map from M to R.?  It first shows the existence of compact subsets that do not allow for such universal approximation guarantee.  Then 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.  The assumptions on the activation functions are general which includes most of the commonly used ones in practice as well.

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.   

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?"   From 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?  The 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.   First, 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.  Second, 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.  Third, they also consider some expressivity properties of simple networks with cosine activations that have width only 1 and depth 3.