Can one (theoretically) train a neural network with fewer training samples than weights? First of all: I know, there is no general number of sample size required to train a neural network. It depends on way too many factors like complexity of the task, noise in the data and so on. And the more training samples I have, the better will be my network. 
But I was wondering: Is it theoretically possible to train a neural network with less training samples than weights, if I assume my task to be "simple" enough? Does anybody know an example where this worked out?
Or will this network almost surely perform poor?
If I consider, for example, polynomial regression, I can't fit a polynomial of degree 4 (i.e. with 5 free parameters) on only 4 data points. 
Is there a similar rule for neural networks, considering my number of weights as the number of free parameters? 
 A: Underdetermined systems are only underdetermined if you impose no other constraints than the data. Sticking with your example, fitting a 4-deg polynomial to 4 data points means you have one degree of freedom not constrained by the data, which leaves you with a line (in coefficient space) of equally good solutions. However, you can use various regularization techniques to make the problem tractable. For example, by imposing a penalty on the L2-norm (i.e. the sum of squares) of the coefficients, you ensure that there is always one unique solution with the highest fitness.
Regularization techniques also exist for neural networks, so the short answer to your question is 'yes, you can'. Of particular interest is a technique called "dropout", in which, for each update of the weights, you randomly 'drop' a certain subset of nodes from the network. That is, for that particular iteration  of the learning algorithm, you pretend these nodes don't exist. Without dropout, the net can learn very complex representations of the input that depend on all the nodes working together just right. Such representations are likely to 'memorize' the training data, rather than finding patterns that generalize. Dropout ensures that the network cannot use all nodes at once to fit the training data; it has to be able to represent the data well even when some nodes are missing, and so the representations it comes up with are more robust. 
Also note that when using dropout, the degrees of freedom at any given point during training can actually be smaller than the number of training samples, even though in total you're learning more weights than training samples. 
A: People do that all the time with large networks. For example, the famous AlexNet network has about 60 million parameters, while the ImageNet ILSVRC it was originally trained on has only 1.2 million images.
The reason you don't fit a 5-parameter polynomial to 4 data points is that it can always find a function that exactly fits your data points, but does nonsensical things elsewhere. Well, as was noted recently, AlexNet and similar networks can fit arbitrary random labels applied to ImageNet and simply memorize them all, presumably because they have so many more parameters than training points. But something about the priors of the network combined with the stochastic gradient descent optimization process means that, in practice, these models can still generalize to new data points well when you give them real labels. We still don't really understand why that happens.
