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?