Geometric methods in the analysis of Glivenko-Cantelli classes

Shahar Mendelson

doi:10.1007/3-540-44581-1_17

Geometric methods in the analysis of Glivenko-Cantelli classes

Shahar Mendelson^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

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 ≤ p < ∞ 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.

Original language	English
Title of host publication	Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings
Editors	David Helmbold, Bob Williamson
Publisher	Springer Verlag
Pages	256-272
Number of pages	17
ISBN (Print)	9783540423430
DOIs	https://doi.org/10.1007/3-540-44581-1_17
Publication status	Published - 2001
Event	14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 - Amsterdam, Netherlands Duration: 16 Jul 2001 → 19 Jul 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2111
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001
Country/Territory	Netherlands
City	Amsterdam
Period	16/07/01 → 19/07/01

Access to Document

10.1007/3-540-44581-1_17

Cite this

Mendelson, S. (2001). Geometric methods in the analysis of Glivenko-Cantelli classes. In D. Helmbold, & B. Williamson (Eds.), Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings (pp. 256-272). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2111). Springer Verlag. https://doi.org/10.1007/3-540-44581-1_17

Mendelson, Shahar. / Geometric methods in the analysis of Glivenko-Cantelli classes. Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings. editor / David Helmbold ; Bob Williamson. Springer Verlag, 2001. pp. 256-272 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{605eab14fcb84bee815875b18eb0d909,

title = "Geometric methods in the analysis of Glivenko-Cantelli classes",

abstract = "We use geometric methods to investigate several fundamental problems in machine learning. We present a new bound on the Lp coveringn umbers of Glivenko-Cantelli classes for 1 ≤ p < ∞ 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.",

author = "Shahar Mendelson",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 ; Conference date: 16-07-2001 Through 19-07-2001",

year = "2001",

doi = "10.1007/3-540-44581-1_17",

language = "English",

isbn = "9783540423430",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "256--272",

editor = "David Helmbold and Bob Williamson",

booktitle = "Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings",

address = "Germany",

}

Mendelson, S 2001, Geometric methods in the analysis of Glivenko-Cantelli classes. in D Helmbold & B Williamson (eds), Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2111, Springer Verlag, pp. 256-272, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, Netherlands, 16/07/01. https://doi.org/10.1007/3-540-44581-1_17

Geometric methods in the analysis of Glivenko-Cantelli classes. / Mendelson, Shahar.
Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings. ed. / David Helmbold; Bob Williamson. Springer Verlag, 2001. p. 256-272 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2111).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Geometric methods in the analysis of Glivenko-Cantelli classes

AU - Mendelson, Shahar

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - We use geometric methods to investigate several fundamental problems in machine learning. We present a new bound on the Lp coveringn umbers of Glivenko-Cantelli classes for 1 ≤ p < ∞ 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.

AB - We use geometric methods to investigate several fundamental problems in machine learning. We present a new bound on the Lp coveringn umbers of Glivenko-Cantelli classes for 1 ≤ p < ∞ 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.

UR - http://www.scopus.com/inward/record.url?scp=23044525499&partnerID=8YFLogxK

U2 - 10.1007/3-540-44581-1_17

DO - 10.1007/3-540-44581-1_17

M3 - Conference contribution

SN - 9783540423430

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 256

EP - 272

BT - Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings

A2 - Helmbold, David

A2 - Williamson, Bob

PB - Springer Verlag

T2 - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001

Y2 - 16 July 2001 through 19 July 2001

ER -

Mendelson S. Geometric methods in the analysis of Glivenko-Cantelli classes. In Helmbold D, Williamson B, editors, Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings. Springer Verlag. 2001. p. 256-272. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44581-1_17

Geometric methods in the analysis of Glivenko-Cantelli classes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this