Train Neural network with infinite amount of data [closed]

Question

Does a sufficiently complex neural network guarantee to find the optimal solution, given an infinite amount of data and the back propagation technique for training?

In other words, given an infinite amount of training data, can neural network get out of local minima and approaches optimal state?

The question is purely theoretical.

Update: It is obvious that a proper neural net with optimal set of weights (in some occasions num of neurons should go to infinity though) can approximate any well-defined function. However, in practice we do not have that optimal set of weights. Those weights are approximated by a training method of choice. The most commonly used method is back-propagation. Now the question was when the number of training samples grows, does the neural net converge to the Bayes rule? In other words, is it a universally consistent classifier? the answer seems to be no. When it gets stuck in local minima no matter how much you increase the training set, it will never get out of it (when using BP as a training method).

you may wanna look at this paper: , (Farago,93)"strong universal consistency of neural network classifiers"

Update2: Perhaps, my update was not clear since I keep getting wikipedia pages as answer: Hope this one finally clarifies:

As I said in my original question, stochastic gradient descent (or perhaps other more complex choices) with back-propagation is going to be used to train the network. This means the weights are not optimal (optimality in the sense that the network may not obtain the Bayes err rate). We also have infinite amount of data which translates to learning in the limit or online learning framework. But to keep it simple, instead of having infinite amount of data, we may assume we have finite but arbitrary large set of data.

The question is, whether the performance of a neural network in theory can now converge to Bayes rate? using any known regularization method such as dropout (which somehow is equivalent to bagging), varying the network structure during training (adding or removing layers, increasing the number of neurons etc), early-stopping and any meta algorithm to sample from this large data-set, or anything else you can think of, are allowed.

PS: Many learning methods are universally consistent meaning that as the number of training samples grows, they guarantee to converge to something good (usually Bayes rate or $\epsilon$ neighborhood of it). I am surprised if we don't have any interesting theorem in that respect for Neural Networks.

Answer 1

You are asking about an "infinite" set of data. The trouble with this question is that backpropagation (BP) is only applicable to a finite set of data (or a finite sample of an infinite population), which is iterated over repeatedly many times in order to converge to a minimum on the error curve. BP is simply not defined for an infinite set of data (outside of batch sampling), because repeated iteration over an infinite set of data is a undefined.

The answer to your question for a finite sample of data depends on the weights used to initialize the BP and how you are defining "optimal."

• In the first regard, since the BP algorithm blindly follows the error curve gradient, it is vulnerable to get stuck in local minima, and by definition of the gradient there is no way out unless you reinitialize the weights.

• In the second regard, optimality may be defined many ways. For example, it may simply stipulate producing an output error less than some $\varepsilon$ for all training data presented. Or your definition may reward generality of a model by placing less constraint on the error and instead use a threshold on some economic formula based on the likelihood of a data point together with the output error that it produces. Or you might invent some other definition.

Allowing for an infinite number of initial guesses and taking the first definition of "optimal" provided above, then it seems clear to me that Siegelmann and Sontag's theorem of universal approximation guarantees a "yes" answer to the finite-data question. But as D.W. remarked, this isn't very useful in practice.

For a trivial but illuminating example, a neural net may "universally approximate" a completely random stream of data for some finite set of training points, and then proceed to fail any and all optimality definitions for data points outside that set. Real world data can contain a sufficient degree of randomness to render the possibility of satisfying an optimality constraint based on non-training data pretty much indeterminate.

Answer 2

There's a standard theorem saying that any function can be approximated arbitrarily well by a multi-layer perceptron-based neural network, if given enough training data and enough layers and enough neurons. However, this theorem isn't terribly useful or relevant to practice, as it doesn't make any promises about how many layers or neurons or training samples are needed. See https://en.wikipedia.org/wiki/Artificial_neural_network#Theoretical_properties.