Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard

Author: Jiri Sima .

Source: Lecture Notes in Artificial Intelligence Vol. 2225, 2001, 92 - 105.

Abstract. We first present a brief survey of hardness results for training feedforward neural networks. These results are then completed by the proof that the simplest architecture containing only a single neuron that applies the standard (logistic) activation 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 relative quadratic training error within 1 or its average (over a training set) within 13/(31n) of its infimum proves to be NP-hard. Hence, the well-known back-propagation learning algorithm appears to be not efficient even for one neuron which has negative consequences in constructive learning.

©Copyright 2001 Springer