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.

  • 1
    $\begingroup$ What does "given an infinite amount of data" mean? Most computation models don't have any mechanism for infinite inputs. How would you give an infinite amount of data to a neural network in finite time? $\endgroup$ – David Richerby Jul 29 '15 at 12:54
  • 1
    $\begingroup$ What does it mean to train a neural network for an infinite amount of time? $\endgroup$ – David Richerby Jul 29 '15 at 14:41
  • 1
    $\begingroup$ The question needs to be defined more carefully so that we can be sure we're answering the question that you have in mind. 1. What do you mean by "optimal"? 2. What kind of neural network? There are many kinds. Are you asking about a single-layer network, or do you want to allow an arbitrary number of layers? Please edit the question accordingly. $\endgroup$ – D.W. Jul 29 '15 at 16:57
  • 1
    $\begingroup$ What research have you done? We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. In your case, this seems to be answered on Wikipedia: en.wikipedia.org/wiki/… - or at least, that's a very relevant result. If the answer to your question is found in the obvious place on WIkipedia, you probably haven't done enough research before asking. $\endgroup$ – D.W. Jul 29 '15 at 16:59
  • 1
    $\begingroup$ I find your update unclear. Your original question talks about an infinite amount of data; the update talks about behaviour as the amount of data grows. Those are completely different questions. Which do you mean? $\endgroup$ – David Richerby Jul 30 '15 at 7:35

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ It's worth noting that the last paragraph applies no matter how arbitrarily large your finite set of data is. Hence you might take the asymptotic case as a substitute for an "infinite" amount of data. This would imply the answer to your question depends wholly on the two bullet points. $\endgroup$ – user35908 Jul 29 '15 at 22:06
  • $\begingroup$ Thanks. but I disagree with the sentence that BP is only applicable to a finite set of data. With stochastic gradient descent and taking mini baches, BP can be applied to infinite set of data, as it is used now a days when data augmentation is employed to virtually create infinite amount of data. $\endgroup$ – TNM Jul 30 '15 at 7:02
  • $\begingroup$ @Tofigh, in a certain sense, I can see where you're coming from. I agree that word "applicable" was poorly chosen, as BP can be "applied" to an infinite set of data by sampling methods, just like you said. I guess my point was that it's impossible to iterate over the entire set of data... no more than it's possible to iterate over the entire set of integers! Therefore (I think) analyses of BP must be based on finite sets, and only extrapolated from there to the asymptotic or "theoretically infinite." Thanks for your comment. $\endgroup$ – user35908 Jul 30 '15 at 7:13
  • $\begingroup$ I see your point. The better way to formulate it is to take a number of training samples to be N and tends it to infinity in order to keep the theorems, proven for finite data valid. I update my question accordingly. Thanks $\endgroup$ – TNM Jul 30 '15 at 7:18

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.

| cite | improve this answer | |
  • $\begingroup$ The question is clear. is nueral network a universally consistent classifier and converges to Bayes rule or not? your answer is irrelevant $\endgroup$ – TNM Jul 30 '15 at 7:08
  • $\begingroup$ @Tofigh, to be fair, you never mentioned those concepts in your original question, so D.W. could not have known to consider them. In good humor, I feel like we're playing pin-the-tail-on-the-donkey (or question) here, as it keeps moving :-) It can be challenging to formulate a question clearly & concisely... I had to basically erase and overhaul my entire (long) first post here on CSSE. $\endgroup$ – user35908 Jul 30 '15 at 7:49
  • $\begingroup$ To me the question is perfectly clear. Given infinite amount of data and a non-optimal way to find the weights, is it possible to get to optimal point (Bayes rule)? but again, I'm the one who pose the question, may be you are right. $\endgroup$ – TNM Jul 30 '15 at 9:07
  • $\begingroup$ It also doesn't say which training method is needed. I don't think we have a general proof that stochastic gradient decent will converge to the global optimum, no matter the layer size or data. $\endgroup$ – Lyndon White Jul 31 '15 at 8:27
  • $\begingroup$ a proper ensemble of NNs each trained with BP do converge to Bayes rule. a variant of dropout or adding/removing layer technique may simulate that. $\endgroup$ – TNM Jul 31 '15 at 9:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.