Complexity of Network Training for Classes of Neural Networks

Abstract

It is known that the problem of training certain specific, very simple neural networks is NP-complete. While such results suggest that training is equally hard for larger, as well as differently configured networks, this conclusion is by no means self-evident. The main result of this paper is that it is NP-complete to train any specific architecture or class of architectures. On the other hand, it is also shown that a simple 4-node network (with two hidden and two output units) can be trained in polynomial time if the target network function is assumed to be surjective. This remains true for networks of any size, on the condition that the number of ouput units is at least equal to the number of units in the first computing layer. Thus, with a mild restriction placed on the class of target functions, training certain large networks may be easier than training smaller ones.