We consider learning on multi-layer neural nets with piecewise polynomial
activation functions and a fixed number k of numerical inputs. We exhibit
arbitrarily large network architectures for which efficient and provably
successful learning algorithms exist in the rather realistic refinement of
Valiant's model for probably approximately correct learning ("PAC-learning")
where no a-priori assumptions are required about the "target function"
(agnostic learning), arbitrary noise is permitted in the training sample,
and the target outputs as well as the network outputs may be arbitrary
reals. The number of computation steps of the learning algorithm LEARN that
we construct is bounded by a polynomial in the bit-length n of the fixed
number of input variables, in the bound s for the allowed bit-length of
weights, in 1/epsilon, where epsilon is some arbitrary given bound for the
true error of the neural net after training, and in 1/delta, where delta is
some arbitrary given bound for the probability that the learning algorithm
fails for a randomly drawn training sample. However the computation time of
LEARN is exponential in the number of weights of the considered network
architecture, and therefore only of interest for neural nets of small size.