Can a neural network with only $1$ hidden layer solve any problem?

Question

Can a network with a single hidden layer of $N$ neurons (where $N\le\infty$) approximate any arbitrary function so that this network’s error approaches $0$ as $N$ approaches $\infty$?

Answer 1

The question asks about "arbitrary functions" and "any problem"; the accepted answer talks only about continuous functions.

The answer to the question as stated now, in both versions, is clearly "no". Some fun counterexamples:

• "Any problem" includes Turing's Entscheidungsproblem, which is famously unsolvable.
• "Arbitrary functions", if you wish to go to a more "mathematical" class of problems, can be very weird. The Ackermann Function is a nice example for a function with a relatively benign definition which can be calculated readily by any kid with basic maths skills (and a lot of time) but which grows at a huge rate (much faster than exponential). It is not primitive recursive, that is, it cannot be computed by a program which consists only of for loops, i.e. where the number of iteration for every loops is known at the beginning of the loop. A neural net with its very simple structure of linear summing neurons and some multiplications is restricted to primitive-recursive functions (at least over an unbounded domain) and cannot approximate that.
• There are discontinous functions which certainly work well as a counter-example too, for example the Dirichlet function.
• As per the comments, and to come down to earth a bit, a simple sin function will do the job of providing a counterexample regarding UATs, as well.

Answer 2

The questions as stated ask "Can a neural network solve and problem?" and "Can a neural network approximate any arbitrary function?" The answer to both of these questions is "No, there is no such theorem."

However, it's common for people learning about neural networks for the first time to mis-state the so-called "universal approximation theorems," which provide the specific technical conditions under which a neural network can approximate a function. OP's questions appear to allude to some version of the Cybenko UAT. Here's a statement of the Cybenko UAT from Wikipedia.

Fix a continuous function $\sigma:\mathbb{R}\rightarrow \mathbb{R}$(activation function) and positive integers $d,D$. The function $\sigma$ is not a polynomial if and only if, for every continuous function function $f:\mathbb{R}^d\to\mathbb{R}^D$ (target function), every compact subset $K$ of $\mathbb{R}^d$, and every $\epsilon >0 $ there exists a continuous function $f_{\epsilon}:\mathbb{R}^d\to\mathbb{R}^D$ (the layer output) with representation: $$ f_{\epsilon} = W_2 \circ \sigma \circ W_1, $$ where $W_2,W_1$ are composable affine maps and $\circ$ denotes component-wise composition, such that the approximation bound: $$ \sup_{x \in K}\, \| f( x ) - f_{\epsilon} ( x ) \| < \varepsilon $$ holds for any $\epsilon$ arbitrarily small (distance from $f$ to $f_\epsilon$ can be infinitely small).

So it's not that any function can be approximated -- the function must be continuous. The error is only smaller than $\epsilon$ on a certain compact subset $K$, and for some unspecified $D$.

In a practical setting where you have some data and you'd like to estimate a neural network, the Cybenko UAT is silent -- it doesn't tell you how to go about estimating $W_2, W_1$, nor does it tell you how to choose the width $D$ of the hidden layer, to achieve this precision.

And finally, achieving small approximation error to certain kinds of functions is not the same as "solving any problem."

(There are a number of approximation theorems for NNs, which reach different conclusions (but are similar in theme) and have different hypotheses.)

Answer 3

The other answers have already mentioned the Universal approximation theorem and that, in strictly mathematical sense, it does not apply to all the functions and it approximates only to the predefined level of error.

However, there is a different way to interpret the question: if a single layer network can approximate any function (satisfying criteria of the UAT) to any required degree of precision, why do we use multilayer networks? The answer is that, given a specified precision, the single layer network may have to be very big and/or may take a very long time to train. Multilayer networks can be smaller and can be trained faster (provided that we use appropriate techniques, such as the backpropagation algorithm).

Answer 4

More comments about "network’s error approaches 0"

There is an important concept about Bayes error rate. Even most powerful model may achieve very high error rates, just because there are large irreducible error.

As an example example, think about if we have large amount of data that have exactly same feature but different label.

Answer 5

The canonical paper for this is Hornik, (1989), for a pdf.

The paper demonstrates that given a neural net with a single layer of sufficient number of nodes, where the activation function is a 'squashing' function, we may approximate any Borel measurable function to arbitrary accuracy.

NB. a net with ReLU activation functions does have this property, as we can make a squashing function from a pair of ReLU function https://papers.nips.cc/paper/2018/file/03bfc1d4783966c69cc6aef8247e0103-Paper.pdf