The computational intractability of training sigmoidal neural networks
- 1 January 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 43 (1) , 167-173
- https://doi.org/10.1109/18.567673
Abstract
We demonstrate that the problem of approximately interpolating a target function by a neural network is computationally intractable. In particular the interpolation training problem for a neural network with two monotone Lipschitzian sigmoidal internal activation functions and one linear output node is shown to be NP-hard and NP-complete if the internal nodes are in addition piecewise ratios of polynomials. This partially answers a question of Blum and Rivest (1992) concerning the NP-completeness of training a logistic sigmoidal 3-node network. An extension of the result is then given for networks with n monotone sigmoidal internal nodes and one convex output node. This indicates that many multivariate nonlinear regression problems may be computationally infeasibleKeywords
This publication has 10 references indexed in Scilit:
- Good weights and hyperbolic kernels for neural networks, projection pursuit, and pattern classification: Fourier strategies for extracting information from high-dimensional dataIEEE Transactions on Information Theory, 1994
- On a learnability question associated to neural networks with continuous activations (extended abstract)Published by Association for Computing Machinery (ACM) ,1994
- Computational limitations on training sigmoid neural networksInformation Processing Letters, 1993
- Universal approximation bounds for superpositions of a sigmoidal functionIEEE Transactions on Information Theory, 1993
- Training a 3-node neural network is NP-completeNeural Networks, 1992
- Feedforward nets for interpolation and classificationJournal of Computer and System Sciences, 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
- Constructive approximations for neural networks by sigmoidal functionsProceedings of the IEEE, 1990
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- The densest hemisphere problemTheoretical Computer Science, 1978