ML Anthology

An Improved VC Dimension Bound for Sparse Polynomials

Michael Schmitt
COLT 2004 pp. 393-407
doi:10.1007/978-3-540-27819-1_27 /colt/2004/schmitt2004colt-improved/

Abstract

We show that the function class consisting of k -sparse polynomials in n variables has Vapnik-Chervonenkis (VC) dimension at least nk +1. This result supersedes the previously known lower bound via k -term monotone disjunctive normal form (DNF) formulas obtained by Littlestone (1988). Moreover, it implies that the VC dimension for k -sparse polynomials is strictly larger than the VC dimension for k -term monotone DNF. The new bound is achieved by introducing an exponential approach that employs Gaussian radial basis function (RBF) neural networks for obtaining classifications of points in terms of sparse polynomials.

PDF COLT Semantic Scholar

Cite

Text

Schmitt. "An Improved VC Dimension Bound for Sparse Polynomials." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_27

Markdown

[Schmitt. "An Improved VC Dimension Bound for Sparse Polynomials." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/schmitt2004colt-improved/) doi:10.1007/978-3-540-27819-1_27

BibTeX

@inproceedings{schmitt2004colt-improved,
  title     = {{An Improved VC Dimension Bound for Sparse Polynomials}},
  author    = {Schmitt, Michael},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2004},
  pages     = {393-407},
  doi       = {10.1007/978-3-540-27819-1_27},
  url       = {https://mlanthology.org/colt/2004/schmitt2004colt-improved/}
}