Deep, Skinny Neural Networks are not Universal Approximators

Introduction

Neural networks have become the model of choice in a variety of machine learning applications, due to their flexibility and generality. However, selecting network architectures and other hyperparameters is typically a matter of trial and error. To make the choice of neural network architecture more straightforward, we need to understand the limits of each architecture, both in terms of what kinds of functions any given network architecture can approximate and how those limitations impact its ability to learn functions within those limits.

A number of papers have shown that neural networks with a single hidden layer are a universal approximator, i.e. that they can approximate any continuous function on a compact domain to arbitrary accuracy if the hidden layer is allowed to have an arbitrarily high dimension. In practice, however, the neural networks that have proved most effective tend to have a large number of relatively low-dimensional hidden layers. This raises the question of whether neural networks with an arbitrary number of hidden layers of bounded dimension are also a universal approximator.

In this paper we demonstrate a fairly general limitation on functions that can be approximated with the $L^{\infty}$ norm on compact subsets of a Euclidean input space by layered, fully-connected feed-forward neural networks of arbitrary depth and activation functions from a broad family including sigmoids and ReLus, but with layer widths bounded by the dimension of the input space. By a layered network, we mean that hidden nodes are grouped into successive layers and each node is only connected to nodes in the previous layer and the next layer. The constraints on the functions are defined in terms of topological properties of the level sets in the input space.

This analysis is not meant to suggest that deep networks are worse than shallow networks, but rather to better understand how and why they will perform differently on different data sets. In fact, these limitations may be part of the reason deep nets have proven more effective on datasets whose structures are compatible with these limitations.

By a level set, we mean the set of all points in the input space that the model maps to a given value in the output space. For classification models, a level set is just a decision boundary for a particular cutoff. For regression problems, level sets don’t have a common interpretation.

The main result of the paper, Theorem 1, states that the deep, skinny neural network architectures described above cannot approximate any function with a level set that is bounded in the input space. This can be rephrased as saying that for every function that can be approximated, every level set must be unbounded, extending off to infinity.

While a number of recent papers have made impressive progress in understanding the limitations of different neural network architectures, this result is notable because it is independent of the number of layers in the network, and because the limitations are defined in terms of a very simple topological property. Topological tools have recently been employed to study the properties of data sets within the field known as Topological Data Analysis , but this paper exploits topological ideas to examine the topology of the models themselves. By demonstrating topological constraints on a widely used family of models, we suggest that there is further potential to apply topological ideas to understand the strengths and weaknesses of algorithms and methodologies across machine learning.

After discussing the context and related work in Section 2, we introduce the basic definitions and notation in Section 3, then state the main Theorem and outline the proof in Section 4. The detailed proof is presented in Sections 5 and 6. We present experimental results that demonstrate the constraints in Section 7, then in Section 8 we present conclusions from this work.

Related Work

A number of papers have demonstrated limitations on the functions that can be approximated by neural networks with particular architectures . These are typically presented as asymptotic bounds on the size of network needed to approximate any function in a given family to a given $\varepsilon$.

The closest existing result to Theorem 1 is a recent paper by Nguyen, Mukkamala and Hein which shows that for multi-label classification problems defined by an argmax condition on a higher-dimensional output function, if all the hidden layers of a neural network have dimension less than or equal to the input dimension then the region defining each class must be connected. The result applies to one-to-one activation functions, but could probably be extended to the family of activation functions in this paper by a similar limiting argument.

Universality results have been proved for a number of variants of the networks described in Theorem 1. Rojas showed that any two discrete classes of points can be separated by a decision boundary of a function defined by a deep, skinny network in which each layer has a single perceptron that is connected both to the previous layer and to the input layer. Because of the connections back to the input space, such a network is not layered as defined above, so Theorem 1 doesn’t contradict this result. In fact, to carry out Rojas’ construction with a layered feed-forward network, you would need to put all the perceptrons in a single hidden layer.

Sutskever and Hinton showed that deep belief networks whose hidden layers have the same dimension as the input space can approximate any function over binary vectors. This binary input space can be interpreted as a discrete subset of Euclidean space. So while Theorem 1 does not apply to belief networks, it’s worth noting that any function on a discrete set can be extended to the full space in such a way that the resulting function satisfies the constraints in Theorem 1.

This unexpected constraint on skinny deep nets raises the question of whether such networks are so practically effective despite being more restrictive than wide networks, or because of it. Lin, Tegmark and Rolnick showed that for data sets with information-theoretic properties that are common in physics and elsewhere, deep networks are more efficient than shallow networks. This may be because such networks are restricted to a smaller search space concentrated around functions that model shapes of data that are more likely to appear in practice. Such a conclusion would be consistent with a number of papers showing that there are functions defined by deep networks that can only by approximated by shallow networks with asymptotically much larger number of nodes .

A slightly different phenomenon has been observed for recurrent neural networks, which are universal approximators of dynamic systems . In this setting, Collins, Sohl-Dickstein and Sussillo showed that many differences that have been reported on the performance of RNNs are due to their training effectiveness, rather than the expressiveness of the networks. In other words, the effectiveness of a given family of models appears to have less to do with whether it includes an accurate model, and more to do with whether a model search algorithm like gradient descent is likely to find an accurate model within the search space of possible models.

Terminology and Notation

With this terminology, Hornik et al’s results can be restated as saying that the (non-parametric) model family defined as the union of all families $\mathcal{N}_{\varphi,n_{0},n_{1},1}$ approximates any continuous function. (Here, $\kappa=2$ and $n_{2}=1$.)

We’re interested in deep networks with bounded dimensional layers, so we’ll let $\mathcal{N}^{*}_{\varphi,n}$ be the union of all the model families $\mathcal{N}_{\varphi,n_{0},n_{1},\ldots,n_{\kappa-1},1}$ such that $n_{i}\leq n$ for all $i<\kappa$.

For the main result, we will restrict our attention to a fairly large family of activation functions. We will say that an activation function $\varphi$ is uniformly approximated by one-to-one functions if there is a sequence of continuous, one-to-one functions that converge to $\varphi$ uniformly (not just pointwise).

Note that if the activation function is itself one-to-one (such as a sigmoid) then we can let every function in the sequence be $\varphi$ and it will converge uniformly. For the ReLu function, we need to replace the the large horizontal portion with a function such as $\frac{1}{n}\arctan(x)$. Since this function is one-to-one and negative for $x<0$, each function in this sequence will be one-to-one. Since it’s bounded between $-\frac{1}{n}$ and , the sequence will converge uniformly to the ReLu function.

Outline of the Main Result

The main result of the paper is a topological constraint on the level sets of any function in the family of models $\mathcal{N}^{*}_{\varphi,n}$. To understand this constraint, recall that in topology, a set $C$ is path connected if any two points in $C$ are connected by a continuous path within $C$. A path component of a set $A$ is a subset $C\subset A$ that is connected, but is not a proper subset of a larger connected subset of $A$.

The main result of this paper states that deep, skinny neural networks can only approximate functions with unbounded level components. Note that this definition is stricter than just requiring that every level set be bounded. The stricter definition in terms of path components guarantees that the property is preserved by limits, a fact that we will prove, then use in the proof of Theorem 1. Just having bounded level sets is not preserved under limits.

The proof of Theorem 1 consists of two steps. In the first step, described in Section 5, we examine the family of functions defined by deep, skinny neural networks in which the activation is one-to-one and the transition matrices are all non-singular.

We prove two results about this smaller family of functions: First, Lemma 2 states that any function that can be approximated by $\mathcal{N}^{*}_{\varphi,n}$ can be approximated by functions in this smaller family. This is fairly immediate from the assumptions on $\varphi$ and the fact that singular transition matrices can be approximated by non-singular ones.

Second, Lemma 4 states that the level sets of these functions have unbounded level components. The proof of this Lemma is, in many ways, the core argument of the paper and is illustrated in Figure 1. The idea is that any function in this smaller family can be written as a composition of a one-to-one function and a linear projection, as in the top row of the Figure.

As suggested in the bottom row, this implies that each level set/decision boundary in the full function is defined by the intersection of the image of the one-to-one function (the gray patch in the middle) with a hyperplane that maps to a single point in the second function. Intuitively, this intersection extends out to the edges of the gray blob, so its preimage in the original space must extend out to infinity in Euclidean space, i.e. it must be unbounded.

The second part of the proof of Theorem 1, described in Section 5, is Lemma 5 which states that the limit of functions with unbounded level components also has unbounded level components. This is a subtle technical argument, though it should be intuitively unsurprising that unbounded sets cannot converge to bounded sets.

The proof of Theorem 1 is the concatenation of these three Lemmas: If a function can be approximated by $\mathcal{N}^{*}_{\varphi,n}$ then it can be approximated by the smaller model family (Lemma 2), so it can be approximated by functions with unbounded level components (Lemma 4), so it must also have unbounded level components (Lemma 5).

Characterizing level sets of “generic” neural net functions

We will say that a function in $\mathcal{N}^{*}_{\varphi,n}$ is non-singular if $\varphi$ is continuous and one-to-one, $n_{i}=n$ for all $i<k$ and the matrix defined by the weights between each pair of layers is nonsingular. Note that if $\varphi$ is not one-to-one, then $\mathcal{N}^{*}_{\varphi,n}$ will not contain any non-singular functions. If it is one-to-one then $\mathcal{N}^{*}_{\varphi,n}$ will contain a mix of singular and non-singular functions.

Define the model family of non-singular functions $\hat{\mathcal{N}_{n}}$ to be the union of all non-singular functions in families $\mathcal{N}^{*}_{\varphi,n}$ for all activation functions $\varphi$ and a fixed $n$.

If $g$ is approximated by $\mathcal{N}^{*}_{\varphi,n}$ for some continuous activation function $\varphi$ that can be uniformly approximated by one-to-one functions then it is approximated by $\hat{\mathcal{N}_{n}}$.

To prove this Lemma, we will employ a technical result from point-set topology, relying on the fact that a function in $\mathcal{N}^{*}_{\varphi,n}$ can be written as a composition of linear functions defined by the weights between successive layers, and non-linear functions defined by the activation function $\varphi$.

If any of the hidden layers in the network defining $g$ have dimension strictly less than $n$ then we can define the same function with a network in which that layer has dimension exactly $n$, but the weights in and out of the added neurons are all zero. Therefore, we can assume without loss of generality that all the hidden layers in $g$ have dimension exactly $n$, though the linear functions may be singular.

Similarly, we want each $\hat{\nu}_{i}$ to be a direct product of a continuous, one-to-one activation functions. By assumption, $\varphi$ can be approximated by such functions and we can choose the tolerance for this approximation to be small enough that $\hat{\nu}_{i}$ $(\delta,A_{i})$-approximates $\nu_{i}$. In fact, we can choose a single activation function for all the nonlinear layers, on each corresponding compact set.

Characterizing level sets in a limit of functions.

Lemma 2 implies that if $\mathcal{N}^{*}_{\varphi,n}$ is universal then so is $\hat{\mathcal{N}_{n}}$. So to prove Theorem 1, we will show that every function in $\hat{\mathcal{N}_{n}}$ has level sets with only unbounded components, then show that this property extends to any function that it approximates.

All that remains is to show that this property extends to the functions that $\hat{\mathcal{N}_{n}}$ approximates.

If $M$ is a model family in which every function has unbounded level components then any function approximated by $M$ has unbounded level components.

By construction, every point in $F$ is distance $\mu/2$ from $C$ so $F$ is disjoint from $C$. Moreover, since every point in $g^{-1}(y)\setminus C$ is distance at least $\mu$ from $C$, $F$ is disjoint from the rest of $g^{-1}(y)$ as well, so $y$ is in the complement of $g(F)$.

Let $\hat{C}$ be the component of $g^{-1}(U)$ that contains $C$, as indicated on the right of the Figure. Note that this set intersects $\eta_{C}$ but is disjoint from its frontier. So $\hat{C}$ must be contained in $\eta_{C}$, and is therefore bounded as well. In particular, each level set that intersects $\hat{C}$ has a compact component in $\hat{C}$.

Let $x$ be a point in $C\subset\hat{C}$. Since $\hat{C}$ is bounded, there is a value $r$ such that every point in $\hat{C}$ is distance at most $r$ from $x$.

Assume for contradiction that $g$ is approximated by a model family $M$ in which each function has unbounded level components. Choose $R>r$ and let $B_{R}({x})$ be a closed ball of radius $R$, centered at $x$. Because this is a compact set and $g$ is approximated by $M$, we can choose a function $f\in M$ that $(\varepsilon/2,B_{R}({x}))$-approximates $g$.

Then $|f(x)-g(x)|<\varepsilon/2$ so $f(x)\in[y-\varepsilon/2,y+\varepsilon/2]\subset U$ and we will define $y^{\prime}=f(x)$.

Let $g$ be a function that is approximated by $\mathcal{N}^{*}_{\varphi,n}$, where $\varphi$ is a continuous activation function that can be uniformly approximated by one-to-one functions.

By Lemma 2, since $g$ is approximated by $\mathcal{N}^{*}_{\varphi,n}$, it must also be approximated by $\hat{\mathcal{N}_{n}}$. By Lemma 4, every function in $\hat{\mathcal{N}_{n}}$ has bounded level components, so Lemma 5 implies that every function that this family approximates has unbounded level sets. Therefore $g$ has unbounded level sets. ∎

Experiments

To demonstrate the effect of Theorem 1, we used the TensorFlow Neural Network Playground to train two different networks on a standard synthetic dataset with one class centered at the origin of the two-dimensional plane, and the other class forming a ring around it. We trained two neural networks and examined the plot of the resulting functions to characterize the level sets/decision boundaries. In these plots, the decision boundary is visible as the white region between the blue and orange regions defining the two labels.

The first network has six two-dimensional hidden layers, the maximum number of layers allowed in the webapp. As shown in Figure 3(a), the decision boundary is an unbounded curve that extends beyond the region containing all the data points. The ideal decision boundary between the two classes of points would be a (bounded) loop around the blue points in the middle, but Theorem 1 proves that such a network cannot approximate a function with such a level set. A decision boundary such as the one shown in the Figure is as close as it can get. The extra hidden layers allow the decision boundary to curve around and minimize the neck of the blue region, but they do not allow it to pinch off completely.

The second network has a single hidden layer of dimension three - one more than that of the input space. As shown in Figure 3(b), the decision boundary for the learned function is a loop that approximates the ideal decision boundary closely. It comes from the three lines defined by the hidden nodes, which make a triangle that gets rounded off by the activation function. Increasing the dimension of the hidden layer would make the decision boundary rounder, though in this case the model doesn’t need the extra flexibility.

Note that this example generalizes to any dimension $n$, though without the ability to directly graph the results. In other words, for any Euclidean input space of dimension $n$, a sigmoid neural network with one hidden layer of dimension $n+1$ can define a function that cannot be approximated by any deep network with an arbitrary number of hidden layers of dimension at most $n$. In fact, this will be the case for any activation function that is bounded above or below, though we will not include the details of the argument here.

Conclusion

In this paper, we describe topological limitations on the types of functions that can be approximated by deep, skinny neural networks, independent of the number of hidden layers. We prove the result using standard set theoretic topology, then present examples that visually demonstrate the result.

This complements a body of existing literature that has demonstrated various limitations on neural networks that typically take a very different form and are expressed in terms of asymptotic network complexity. We expect that there is a great deal of remaining potential to explore further topological constraints on families of models, and to determine to what extent these topological constraints are simply a different way of describing more fundamental ideas that have been independently demonstrated elsewhere in other frameworks such as information theory.

References