Perspectives of Current Research about the Complexity of Learning on Neural Nets

This paper discusses within the framework of computational learning theory the current state of knowledge and some open problems in three areas of research about learning on feedforward neural nets: -- Neural nets that learn from mistakes -- Bounds for the Vapnik-Chervonenkis dimension of neural nets -- Agnostic PAC-learning of functions on neural nets. All relevant definitions are given in this paper, and no previous knowledge about computational learning theory or neural nets is required. We refer to [RSO] for further introductory material and survey papers about the complexity of learning on neural nets. Throughout this paper we consider the following rather general notion of a (feedforward) neural net