Dimension-Independent Approximation by Neural Networks:How Can we Cope With the Curse of Dimensionality?
by
Marcello Sanguineti
Department of Communications, Computer and System Sciences - DIST - University of Genoa
Coauthors: Vera Kurkova (Academy of Sciences of the Czech Republic)

Many estimates of rates of approximation exhibit the ``curse of dimensionality'' (i.e., the exponential increase of the number of parameters necessary to obtain a given approximation accuracy, with increasing dimension of the argument of the function to be approximated). More specifically, an accuracy of approximation within 1/n on a set of functions of d variables can be guaranteed only using approximating functions with O(n^d) parameters. We introduce neural networks as a nonlinear approximation scheme; since they compute parametrized nonlinear families of functions of a different type than all previously studied nonlinear families, they form a new branch of the field of nonlinear approximation theory. We show that under certain constraints on the functions to be approximated and on the type of hidden units, such networks achieve an accuracy of approximation within 1/n using only O(n^2) hidden units. We discuss how the aforementioned constraints can be formulated in terms of certain norms, tailored to a given neural network class. The comparison with traditional linear approximation schemes is finally addressed.

Date received: January 14, 2000