neural efficiency

[Oscar Ruiz]

Subject: Neural efficiency.

For some time I have been interested in the efficiency  of  neural 
network (NN) fitness, but I have  still  very  little  information 
about this matter -I got a bibliography with  articles  and  books 
about this matter, but I cannot find them here in Spain,  and  the 
mail is (exasperatingly) slow. I have heard that the NN fitness is 
an NP-complete (perhaps even NP-hard) problem. I  know  what  this 
means in discrete problems, but I am not sure  what  it  means  in 
continuous problems, as in the case of a NN  whose  units  have  a 
continuous activation function (e.g.: a sigmoid), where the  exact 
fitness is, in general, impossible.  Efficiency  problems  can  be 
formalized in terms of  Turing  Machines,  which  are  essentially 
discrete objects. But how can it be done with continuous problems?

On the other hand, reference (1) below states that  generally  the 
number of steps needed to optimize a function of n variables, with 
a given relative error, is an exponential function of n (see for a 
more rigorous formulation of this result below). Since  fitting  a 
neural network is equivalent  to  minimizing  its  error  function 
(whose variables are the NN weights), the search for an  efficient 
general method to fit the weights in a NN  is  doomed  to  failure 
(except for some particular cases). I would like to know  if  this 
is right.


Reference:

(1) Nemirovsky et al.: Problem Complexity and Method Efficiency in 
    Optimization (John Wiley & Sons).

(In this book, concrete classes  of  problems  and  the  class  of 
methods corresponding to these problems are  considered.  Each  of 
these methods applied to  the  class  of  problems  considered  is 
characterized by its laboriousness and error, i.e. by upper bounds 
-over the problems of the class- for the number of  steps  in  its 
work on the problem and by the error of the result. The complexity 
N(v) of a given class of problems is defined as the least possible 
laboriousness of a method which solves every problem of the  class 
with a relative error not exceeding v.  The  main  result  is  the 
following: For the complexity N(v) of the class  of  all  extremal 
problems with k-times continuously differential functionals  on  a 
compact field G in E^n, the lower  bound  c(k,G)(1/v)^(n/k)  holds 
both for the ordinary -deterministic- methods of solution and  for 
random-search methods.)


Miguel A. Lerma
Sancho Davila 18
28028 MADRID - SPAIN