On a Learnability Question Associated to Neural Networks with Continuous Activations
Lists
Only you see this
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...