Does a neural network exist that can learn every possible training data?

Question

The universal approximation theorem states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of $R^n$.

Michael Nielsen states

No matter what the function, there is guaranteed to be a neural network so that for every possible input, $x$, the value $f(x)$ (or some close approximation) is output from the network.

So, for continuous functions, this seems plausible. Interestingly, in the same article, Nielsen mentioned "any function".

Later, he writes

However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough.

The last statement leaves open a gap, to ask how well an approximation practically can be.

Let's ignore contradictory input/output training pairs like $f(0)=0$ and $f(0)=1$, which actually don't event represent a function anyway.

Furthermore, assume that the training data is generated randomly, which would practically result in a discontinuous function.

How does a neural network learn such data? Will a learning algorithm always be able to find a neural network that approximates the function represented by the input-output pairs?

Answer 1

The branch of AI research that answers questions like this is called computational learning theory.

For the specific question you have asked, the universal approximation theorem does indeed prove that any function can be modeled by a sufficiently wide neural network. The definition of a function includes the requirement that each input be mapped to exactly one output, so contradictory labels in training data are excluded explicitly.

Here is a rough sketch that can provide an intuition behind why this is true. This is not a proper proof, but it gives you an idea of the power of "finite number of neurons" in a hidden layer:

1. A single neuron can essentially learn to draw a straight line across the space of input features. It outputs a value arbitrarily close to 1 for things on one side of the line, and arbitrarily close to 0 for things on the other side of the line.
2. For any given datapoint, it is possible to enclose the hyper-volume containing that datapoint, and no others by drawing a series of lines in the input space, and defining one side of each line as "inside" the hyper-volume, and the other side as "outside". In 2-d space, this corresponds to drawing the 4 sides of a square around a point.
3. An output neuron learns to draw lines across the outputs of the hidden layer neurons. It can therefore decide to output 1 only when, say, 4 other neurons are all simultaneously active.

It should seem natural then that a sufficiently wide neural network can memorize all of an input pattern. Since memorization is sufficient for "learning" to fit a pattern this should give you an intuition for the ability of neural networks to fit things.