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

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$$?

• I think it's worth noting that "can approximate any continuous function" is distinct from "solve any problem". In fact, being able to approximate any continuous function might be a bad thing, since we can overfit to an arbitrary degree. Notably, this same property of approximating arbitrary continuous functions also holds for polynomials as the degree approaches infinity, and polynomials are notorious for overfitting.
– Him
Commented Feb 9, 2022 at 5:21
• A neural network with 0 hidden layers is identical to logistic regression, which can solve a great many problems. en.wikipedia.org/wiki/… Commented Feb 10, 2022 at 13:55
• Are you sure you only want your inequality $N\le\infty$ to be slack, rather than requiring it to be strict?
– J.G.
Commented Feb 10, 2022 at 16:08

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.
• I don't think the Ackermann function works as a counterexample here. A continuous extension of it could be approximated by a neural network by a (pick your favorite) UAT, at least on some finite domain; the explosive growth of it would just necessitate a large network, I believe. Better examples include pathologically-discontinuous, or for the domain hypothesis of UATs, just sin(x) will do. Commented Feb 10, 2022 at 18:49
– AnoE
Commented Feb 11, 2022 at 8:24

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.)

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).