Training a Single Sigmoidal Neuron Is Hard
Author:
- 1 November 2002
- journal article
- research article
- Published by MIT Press in Neural Computation
- Vol. 14 (11) , 2709-2728
Abstract
We first present a brief survey of hardness results for training feed forward neural networks. These results are then completed by the proof that the simplest architecture containing only a single neuron that applies a sigmoidal activation function σ:K→ [α, β], satisfying certain natural axioms (e.g., the standard (logistic) sigmoid or saturated-linear function), to the weighted sum of n inputs is hard to train. In particular, the problem of finding the weights of such a unit that minimize the quadratic training error within (β—α)2 or its average (over a training set) within—5(β—α)2 /(12n) of its infimum proves to be NP-hard. Hence, the well-known backpropagation learning algorithm appears not to be efficient even for one neuron, which has negative consequences in constructive learning.Keywords
This publication has 19 references indexed in Scilit:
- Training a Sigmoidal Node Is HardNeural Computation, 1999
- The computational intractability of training sigmoidal neural networksIEEE Transactions on Information Theory, 1997
- Back-propagation is not EfficientNeural Networks, 1996
- Classification of linearly nonseparable patterns by linear threshold elementsIEEE Transactions on Neural Networks, 1995
- Robust Trainability of Single NeuronsJournal of Computer and System Sciences, 1995
- On the complexity of training neural networks with continuous activation functionsIEEE Transactions on Neural Networks, 1995
- Loading Deep Networks Is HardNeural Computation, 1994
- Computational limitations on training sigmoid neural networksInformation Processing Letters, 1993
- Feedforward nets for interpolation and classificationJournal of Computer and System Sciences, 1992
- Computational limitations on learning from examplesJournal of the ACM, 1988