Lower bounds on the Vapnik-Chervonenkis dimension of multi-layer threshold networks
Peter L. Bartlett · 1993
We consider the problem of learning in multi-Iayer feed-forward networks of linear threshold units.We show that the Vapnik-Chervonenkis dimension of the class of functions that can be computed by a two-layer threshold network with real inputs IS at least proportional to the number of weights in the network.This result also holds for a large class of two-Iayer networks with binary inputs, and a large class of three-layer networks with real inputs.In Valiant's probably approximately correct learning framework, this implies that the number of examples necessary for learning in these networks is at least linear in the number of weights.This bound is within a log factor of the upper bound.