## DIMACS TR: 99-60

## Hardness of Approximation of the Loading Problem for Multi-layered Feedforward Neural Nets

### Authors: Bhaskar DasGupta and Barbara Hammer

**
ABSTRACT
**

In this paper we deal with the problem of efficient
learning of feedforward neural networks. First,
we consider the case when the objective is to
maximize the ratio r of the correctly classified points
compared to all points in a training set.
We show that, for an arbitrary multilayered threshold network
with varying input dimension and with a constant
n_1 >= 2 neurons in the first
hidden layer, it is NP-hard to approximate r within a relative error
of at most \varepsilon=1/(68 n_1 2^{n_1}+ 136 n_1^3+ 136 n_1^2 +170n_1).
If n_1 >= 3, then the above result is true with
\varepsilon=c(n_1-1)/(5n_1^3+2n_1^32^{n_1}+4n_1^5+4n_1^4) for some
positive constant c, even if restricted to situations
where a solution without any misclassifications exists.
Restricted to architectures with only one hidden layer
and two hidden neurons
approximation of r with relative error at most
1/c is NP-hard even
if either (a) c=2244, the threshold activation function in
the hidden layer is substituted by
the classical sigmoid function, and the situation of
\epsilon-separation of the output classification is assumed, or (b)
c=2380 and the threshold activation
function is substituted by the semilinear activation function commonly used
in the neural net literature.
For a single hidden layer threshold network
with varying input dimension and k hidden nodes,
approximating r within a relative error of at most c/k^5, for some
positive constant c, is NP-hard even if restricted to situations
where the number of examples is at most k^4.
Finally, we consider the case when the objective is to minimize the
failure ratio f in the presence of missclassification
errors.
We show that it is NP-hard to approximate f
within any constant c>1 for a multilayered threshold
network if the input biases are fixed to zero.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-60.ps.gz

DIMACS Home Page