ON THE COMPLEXITY OF TRAINING NEURAL NETWORKS WITH CONTINUOUS ACTIVATION FUNCTIONS

We deal with computational issues of loading a fixed-architecture neur al network with a set of positive and negative examples. This is the f irst result on the hardness of loading a simple three-node architectur e which does not consist of the binary-threshold neurons, but rather u tilizes a particular continuous activation function, commonly used in the neural-network literature. We observe that the loading problem is polynomial-time if the input dimension is constant. Otherwise, however , any possible learning algorithm based on particular fixed architectu res faces severe computational barriers. Similar theorems have already been proved by Megiddo and by Blum and Rivest, to the case of binary- threshold networks only, Our theoretical results lend further suggesti on to the use of incremental (architecture-changing) techniques for tr aining networks rather than fixed architectures. Furthermore, they imp ly hardness of learnability in the probably approximately correct sens e as well.