ML Anthology

Lower Bound on VC-Dimension by Local Shattering

Yossi Erlich, Dan Chazan, Scott Petrack, Avi Levi
NeCo 1997 pp. 771-776
doi:10.1162/NECO.1997.9.4.771 /neco/1997/erlich1997neco-lower/

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.

NeCo Semantic Scholar

Cite

Text

Erlich et al. "Lower Bound on VC-Dimension by Local Shattering." Neural Computation, 1997. doi:10.1162/NECO.1997.9.4.771

Markdown

[Erlich et al. "Lower Bound on VC-Dimension by Local Shattering." Neural Computation, 1997.](https://mlanthology.org/neco/1997/erlich1997neco-lower/) doi:10.1162/NECO.1997.9.4.771

BibTeX

@article{erlich1997neco-lower,
  title     = {{Lower Bound on VC-Dimension by Local Shattering}},
  author    = {Erlich, Yossi and Chazan, Dan and Petrack, Scott and Levi, Avi},
  journal   = {Neural Computation},
  year      = {1997},
  pages     = {771-776},
  doi       = {10.1162/NECO.1997.9.4.771},
  volume    = {9},
  url       = {https://mlanthology.org/neco/1997/erlich1997neco-lower/}
}