ML Anthology

Geometric Methods in the Analysis of Glivenko-Cantelli Classes

Shahar Mendelson
COLT 2001 pp. 256-272
doi:10.1007/3-540-44581-1_17 /colt/2001/mendelson2001colt-geometric/

Abstract

We use geometric methods to investigate several fundamental problems in machine learning. We present a new bound on the L _p coveringn umbers of Glivenko-Cantelli classes for $ 1 \leqslant p < \infty $ in terms of the fat-shatteringdimension of the class, which does not depend on the size of the sample. Usingthe new bound, we improve the known sample complexity estimates and bound the size of the Sufficient Statistics needed for Glivenko-Cantelli classes.

PDF COLT Semantic Scholar

Cite

Text

Mendelson. "Geometric Methods in the Analysis of Glivenko-Cantelli Classes." Annual Conference on Computational Learning Theory, 2001. doi:10.1007/3-540-44581-1_17

Markdown

[Mendelson. "Geometric Methods in the Analysis of Glivenko-Cantelli Classes." Annual Conference on Computational Learning Theory, 2001.](https://mlanthology.org/colt/2001/mendelson2001colt-geometric/) doi:10.1007/3-540-44581-1_17

BibTeX

@inproceedings{mendelson2001colt-geometric,
  title     = {{Geometric Methods in the Analysis of Glivenko-Cantelli Classes}},
  author    = {Mendelson, Shahar},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2001},
  pages     = {256-272},
  doi       = {10.1007/3-540-44581-1_17},
  url       = {https://mlanthology.org/colt/2001/mendelson2001colt-geometric/}
}