Communicated by Nicolo Cesa-Bianchi Agnostic PAC Learning of Functions on Analog Neural Nets

We consider learning on multilayer neural nets with piecewise poly-nomial 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 realis-tic 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 per-mitted 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 vari-ables, in the bound s for the allowed bit-length of weights, in 1 / ~, where E is some arbitrary given bound for the true error of the neural net after training, and in l / h where b 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 archi-tecture, and therefore only of interest for neural nets of small size. This (Maass 1994).