Random subclass bounds

Shahar Mendelson; Petra Philips

doi:10.1007/978-3-540-45167-9_25

Random subclass bounds

Shahar Mendelson^*, Petra Philips

^*Corresponding author for this work

Research output: Contribution to journal › Conference article › peer-review

3 Citations (Scopus)

Abstract

It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is "small" in the sense that the Rademacher averages of this function class are small. Seemingly based on different arguments, generalization bounds were obtained in the compression scheme, luckiness, and algorithmic luckiness frameworks in which the "size" of the function class is not specified a priori. We show that the bounds obtained in all these frameworks follow from the same general principle, namely that coordinate projections of this function subclass evaluated on random samples are "small" with high probability.

Original language	English
Pages (from-to)	329-343
Number of pages	15
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2777
DOIs	https://doi.org/10.1007/978-3-540-45167-9_25
Publication status	Published - 2003
Event	16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003 - Washington, DC, United States Duration: 24 Aug 2003 → 27 Aug 2003

Access to Document

10.1007/978-3-540-45167-9_25

Cite this

@article{92e83134663148f88f5dc4a9fe780b24,

title = "Random subclass bounds",

abstract = "It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is {"}small{"} in the sense that the Rademacher averages of this function class are small. Seemingly based on different arguments, generalization bounds were obtained in the compression scheme, luckiness, and algorithmic luckiness frameworks in which the {"}size{"} of the function class is not specified a priori. We show that the bounds obtained in all these frameworks follow from the same general principle, namely that coordinate projections of this function subclass evaluated on random samples are {"}small{"} with high probability.",

keywords = "Data-dependent complexity, Generalization bounds, Statistical learning theory",

author = "Shahar Mendelson and Petra Philips",

year = "2003",

doi = "10.1007/978-3-540-45167-9_25",

language = "English",

volume = "2777",

pages = "329--343",

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

issn = "0302-9743",

publisher = "Springer Verlag",

note = "16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003 ; Conference date: 24-08-2003 Through 27-08-2003",

}

TY - JOUR

T1 - Random subclass bounds

AU - Mendelson, Shahar

AU - Philips, Petra

PY - 2003

Y1 - 2003

N2 - It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is "small" in the sense that the Rademacher averages of this function class are small. Seemingly based on different arguments, generalization bounds were obtained in the compression scheme, luckiness, and algorithmic luckiness frameworks in which the "size" of the function class is not specified a priori. We show that the bounds obtained in all these frameworks follow from the same general principle, namely that coordinate projections of this function subclass evaluated on random samples are "small" with high probability.

AB - It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is "small" in the sense that the Rademacher averages of this function class are small. Seemingly based on different arguments, generalization bounds were obtained in the compression scheme, luckiness, and algorithmic luckiness frameworks in which the "size" of the function class is not specified a priori. We show that the bounds obtained in all these frameworks follow from the same general principle, namely that coordinate projections of this function subclass evaluated on random samples are "small" with high probability.

KW - Data-dependent complexity

KW - Generalization bounds

KW - Statistical learning theory

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

U2 - 10.1007/978-3-540-45167-9_25

DO - 10.1007/978-3-540-45167-9_25

M3 - Conference article

AN - SCOPUS:9444278349

SN - 0302-9743

VL - 2777

SP - 329

EP - 343

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

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

T2 - 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003

Y2 - 24 August 2003 through 27 August 2003

ER -

Random subclass bounds

Abstract

Access to Document

Other files and links

Fingerprint

Cite this