ML Anthology

Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

César Luis Alonso, José Luis Montaña
ALT 2007 pp. 107-119
doi:10.1007/978-3-540-75225-7_12 /alt/2007/alonso2007alt-vapnikchervonenkis/

Abstract

We provide upper bounds for the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers whose membership tests are programs described by bounded-depth arithmetic networks. Our upper bounds are of the kind O ( k ^2 d ^2), where d is the depth of the network (representing the parallel running time) and k is the number of parameters needed to codify the concept. This bound becomes O ( k ^2 d ) when membership tests are described by Boolean-arithmetic circuits. As a consequence we conclude that families of concepts classes having parallel polynomial time algorithms expressing their membership tests have polynomial VC dimension.

PDF ALT Semantic Scholar

Cite

Text

Alonso and Montaña. "Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations." International Conference on Algorithmic Learning Theory, 2007. doi:10.1007/978-3-540-75225-7_12

Markdown

[Alonso and Montaña. "Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations." International Conference on Algorithmic Learning Theory, 2007.](https://mlanthology.org/alt/2007/alonso2007alt-vapnikchervonenkis/) doi:10.1007/978-3-540-75225-7_12

BibTeX

@inproceedings{alonso2007alt-vapnikchervonenkis,
  title     = {{Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations}},
  author    = {Alonso, César Luis and Montaña, José Luis},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2007},
  pages     = {107-119},
  doi       = {10.1007/978-3-540-75225-7_12},
  url       = {https://mlanthology.org/alt/2007/alonso2007alt-vapnikchervonenkis/}
}