M. Kon and L. Plaskota
Complexity of neural network approximation with limited information:
a worst case approach
Abstract.
In neural network theory the complexity of constructing networks to
approximate input-output functions is of interest. We study this in
the more general context of approximating elements $f$ of a normed space
$F$ using partial information about $f$. We assume information about $f$
and the size of the network are limited, as is typical in radial basis
function networks. We show complexity can be essentially split into two
independent parts, information $\varepsilon$-complexity and neural
$\varepsilon$-complexity.
We use a worst case setting, and integrate elements of information-based
complexity and nonlinear approximation. We consider deterministic and/or
randomiazed approximations using information possibly corrupted by noise.
The results are illustrated by examples including approximation by
piecewise polynomial networks.