Neural Computation
May 15, 1997, Vol. 9, No. 4, Pages 771-776
(doi: 10.1162/neco.1997.9.4.771)
Lower Bound on VC-Dimension by Local Shattering
Article PDF (48.88 KB)
Abstract
We show that the VC-dimension of a smoothly parameterized function class is not less than the dimension of any manifold in the parameter space, as long as distinct parameter values induce distinct decision boundaries. A similar theorem was published recently and used to introduce lower bounds on VC-dimension for several cases (Lee, Bartlett, & Williamson, 1995). This theorem is not correct, but our theorem could replace it for those cases and many other practical ones.