VC dimension, fat-shattering dimension, rademacher averages, and their applications

Vladimir V. V'yugin

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

3 Citations (Scopus)


We consider several complexity measures which capture the difficulty of learning under the i.i.d. assumption. Among these measures are growth function and VC dimension, covering number and fat-shattering dimension, and Rademacher complexity from statistical learning theory. Relationships among these complexity measures, their connection to learning, and tools for bounding them are provided. For each complexity measure, a uniform upper bound on the generalization error of classification problems is presented.

Original languageEnglish
Title of host publicationMeasures of Complexity
Subtitle of host publicationFestschrift for Alexey Chervonenkis
PublisherSpringer International Publishing
Number of pages18
ISBN (Electronic)9783319218526
ISBN (Print)9783319218519
Publication statusPublished - 5 Oct 2015
Externally publishedYes


Dive into the research topics of 'VC dimension, fat-shattering dimension, rademacher averages, and their applications'. Together they form a unique fingerprint.

Cite this