On a Learnability Question Associated to Neural Networks with Continuous Activations

Bhaskar DasGupta, Hava T. Siegelmann, Eduardo D. SontagScholarWorks@UMassAmherst 1994

Abstract

) z Bhaskar DasGupta y Department of Computer Science University of Minnesota Minneapolis, MN 55455-0159 [email protected] Hava T. Siegelmann Department of Computer Science Bar-Ilan University Ramat-Gan 52900, Israel [email protected] Eduardo Sontag Department of Mathematics Rutgers University New Brunswick, NJ 08903 [email protected] Abstract This paper deals with learnability of concept classes defined by neural networks, showing the hardness of PAC-learning (in the complexity, not merely information-theoretic sense) for networks with a particular class of activation. The obstruction lies not with the VC dimension, which is known to grow slowly; instead, the result follows the fact that the loading problem is NP-complete. (The complexity scales badly with input dimension; the loading problem is polynomial-time if the input dimension is constant.) Similar and well-known theorems had already been proved by Megiddo and by Blum and Rivest, for binary-thre...
BibTeX
@inproceedings{dasgupta1994learnability,
  author = {Bhaskar DasGupta and Hava T. Siegelmann and Eduardo D. Sontag},
  title = {{On a Learnability Question Associated to Neural Networks with Continuous Activations}},
  booktitle = {ScholarWorks@UMassAmherst},
  year = {1994},
}

Loading related content...

Figure