On the complexity of training neural networks with continuous activation functions
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 6 (6) , 1490-1504
- https://doi.org/10.1109/72.471360
Abstract
Deals with computational issues of loading a fixed-architecture neural network with a set of positive and negative examples. This is the first result on the hardness of loading a simple three-node architecture which does not consist of the binary-threshold neurons, but rather utilizes a particular continuous activation function, commonly used in the neural-network literature. The authors observe that the loading problem is polynomial-time if the input dimension is constant. Otherwise, however, any possible learning algorithm based on particular fixed architectures 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. The authors' theoretical results lend further suggestion to the use of incremental (architecture-changing) techniques for training networks rather than fixed architectures. Furthermore, they imply hardness of learnability in the probably approximately correct sense as well.Keywords
This publication has 19 references indexed in Scilit:
- Computational limitations on training sigmoid neural networksInformation Processing Letters, 1993
- Finiteness results for sigmoidal “neural” networksPublished by Association for Computing Machinery (ACM) ,1993
- Training a 3-node neural network is NP-completeNeural Networks, 1992
- A Simple Lemma on Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network TrainingThe Annals of Statistics, 1992
- Complexity results on learning by neural netsMachine Learning, 1991
- What Size Net Gives Valid Generalization?Neural Computation, 1989
- On the complexity of loading shallow neural networksJournal of Complexity, 1988
- An introduction to computing with neural netsIEEE ASSP Magazine, 1987
- On the learnability of Boolean formulaePublished by Association for Computing Machinery (ACM) ,1987
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977