Scale-sensitive dimensions, uniform convergence, and learnability

Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, David Haussler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Scopus citations

Abstract

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages292-301
Number of pages10
ISBN (Print)0818643706
StatePublished - Dec 1 1993
Externally publishedYes
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Publication series

NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Scale-sensitive dimensions, uniform convergence, and learnability'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Ben-David, S., Cesa-Bianchi, N., & Haussler, D. (1993). Scale-sensitive dimensions, uniform convergence, and learnability. In Anon (Ed.), Annual Symposium on Foundatons of Computer Science (Proceedings) (pp. 292-301). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.