# Does a converging (deep) neural network exist for every possible training data?

Let's assume some arbitrary labeled training data. Maybe generated just completely random. Does a neural network exist which converges on the training data?

With convergence, I mean that the network describes the training data to high accuracy. I don't want to define high accuracy because this might limit the answers I get.

Further, the question is related to: For every training data does a neural network exist which finds some kind of pattern to achieve high accuracy?

Or to turn it around, given some accuracy acc in the interval [0,1] and some arbitrary training data, can I find a neural network which will at least reach the given accuracy?
The last one is theoretical and practical question. What would it take to reach the given accuracy. Is it possible in a few minutes for an experienced AI expert or are we talking about centuries of training which is practically unrealistic (currently without quantum computing).

Edit: As mentioned in the comments, for arbitrary pairs of input/ouput values it is simple to construct a counter example such that there is no neural network to solve the problem.
What if the input must be unique, such that the input values can only occur once with arbitrary labels?

Edit 2: 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 Rn, ... (see https://en.wikipedia.org/wiki/Universal_approximation_theorem).

Further, 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 (see http://neuralnetworksanddeeplearning.com/chap4.html).

So for continous functions this seems plausible. Interestingly Nielsen mentioned any function, which he also explains as problematic and he basically gets to continous functions which might approximate non continous functions well enough.

My problem here is, that the theorem assumes that there is some kind of (continous) function. And my question is basically, does a neural network - or more precise the learning algorithm - always find some pattern given some random input? So, can a neural network theoretically be used to show that a correlation between input/output exists or do examples exist where the network will never converge.

To ask it differently: Will I always be able to find a network which finds the most absurd correlations I want it to find?

• Simple counterexample showing that there are training data for which this isn't possible: consider a network with one input and one output. Train it with the data (0,0) and (0,1). Now, which output should it learn? – Hans-Martin Mosner Nov 7 '19 at 12:18
• @Hans-MartinMosner Can you please elaborate your comment a bit? With (0,1) you mean, input value 0 and output value 1? So the same input has two different labels? If thats what you meant, I think I understand your argument, but its not what I meant. The idea was that each pair of training input and label is unique, so e.g. an image of a cat is only a cat and not a cat and a dog – John Doe Nov 7 '19 at 13:21
• Well I see that my question allows your answer. I'll edit my question to add a more plausible assumption – John Doe Nov 7 '19 at 13:22
• The real problem with the question is that even when you tune it to avoid the loophole I've shown it is too open-ended. There are many classes of neural networks, many training algorithms, possibly many more that haven't been invented yet, so it is likely impossible to find a definitive answer. – Hans-Martin Mosner Nov 7 '19 at 13:41
• @Hans-MartinMosner I've edited the question. Many thanks for your scepticism – John Doe Nov 7 '19 at 14:20