On the complexity of training neural networks with continuous activation functions. DasGupta, B.; Siegelmann, H.; and Sontag, E. IEEE Trans. Neural Networks, 6:1490–1504, 1995. abstract bibtex Blum and Rivest showed that any possible neural net learning algorithm based on fixed architectures faces severe computational barriers. This paper extends their NP-completeness result, which applied only to nets based on hard threshold activations, to nets that employ a particular continuous activation. In view of neural network practice, this is a more relevant result to understanding the limitations of backpropagation and related techniques.
@ARTICLE{DasGupta-TNN,
AUTHOR = {B. DasGupta and H.T. Siegelmann and E.D. Sontag},
JOURNAL = {IEEE Trans. Neural Networks},
TITLE = {On the complexity of training neural networks with
continuous activation functions},
YEAR = {1995},
OPTMONTH = {},
OPTNOTE = {},
OPTNUMBER = {},
PAGES = {1490--1504},
VOLUME = {6},
KEYWORDS = {neural networks, analog computing, theory of computing,
neural networks, computational complexity, machine learning},
PDF = {../../FTPDIR/complexity-training.pdf},
ABSTRACT = { Blum and Rivest showed that any possible neural net
learning algorithm based on fixed architectures faces severe
computational barriers. This paper extends their NP-completeness
result, which applied only to nets based on hard threshold
activations, to nets that employ a particular continuous activation.
In view of neural network practice, this is a more relevant result to
understanding the limitations of backpropagation and related
techniques. }
}