Rate of Approximation Results Motivated by Robust Neural Network Learning

Abstract

The set of functions which a single hidden layer neural network can approximate is increasingly well understood, yet our knowledge of how the approximation error depends upon the number of hidden units, i.e. the rate of approximation, remains relatively primitive. Barron [1991] and Jones [1992] give bounds on the rate of approximation valid for Hilbert spaces. We derive bounds for L spaces, 1 < p < m, re-covering the 0(1 /&) bounds of Barron and Jones for the case p = 2. The results were motivated in part by the desire to understand approximation in the more “robust” (resistant to exemplar noise) LP, 1 ~ p <2 norms. Consider the task of approximating a given target function f by a linear combination of n functions from a set S. For example, S may be the set of possible sig-moidal activation functions, g : ~d - ~[% 6 ~d, b E ~, s.t. g(z) = a(a . z + b), in which case the approx-imants are single hidden layer neural networks with a linear output layer. It is known that under very weak conditions on IS (it must be Riemann integrable and nonpolynomial), the linear span of S is dense in the set of continuous functions on compact subsets of ~d (i.e. for all positive c there is a linear combination of functions in S which can approximate any continuous function to within