Universal Approximator Results

[Thomas M. Breuel]

Arun Jagota writes:
 > A question was raised some time back that since universal approximator 
 > results establish no new bounds on computability (one result is as good 
 > as another in a computability sense), what then is their significance.
 > Don't such results for k-hidden layer networks show, additionally,
 > that the represented function can be _evaluated_ on a point in it's
 > domain in 
 > 
 > (k+1)  inner-product       +        k    hidden-layer function eval
 > steps on a suitable abstract machine.
 > 
 > Doesn't that provide a strong result on the running time,
 > as compared with Church's thesis which says, that any algorithm
 > (effective procedure) can be programmed on a Turing m/c but doesn't
 > put a bound on the running time.

The claim is still true: "computability" says nothing about time
complexity, space complexity, or parallel complexity. Therefore, from
a computability point of view, it makes no difference whatsoever
whether you prove that something is computable via networks or via a
Turing machine, even if the Turing machine takes much longer.

There are two other issues here: the "universal approximator" results
talk about approximating a real function, not computing a real
function, and, also, all the arithmetic here is real arithmetic, so
a comparison between complexity on a Turing machine and the arithmetic
complexity on the network is non-trivial.

						Thomas.