On a Learnability Question Associated to Neural Networks with Continuous Activations
Bhaskar DasGupta, Hava T. Siegelmann, Eduardo D. Sontag · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · 1994
) 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...