title: A local Vapnik-Chervonenkis complexity.
abstract: We define in this work a new localized version of a Vapnik-Chervonenkis (VC) complexity, namely the Local VC-Entropy, and, building on this new complexity, we derive a new generalization bound for binary classifiers. The Local VC-Entropy-based bound improves on the original Vapnik's results because it is able to discard those functions that, most likely, will not be selected during the learning phase. The result is achieved by applying the localization principle to the original global complexity measure, in the same spirit of the Local Rademacher Complexity. By exploiting and improving a recently developed geometrical framework, we show that it is also possible to relate the Local VC-Entropy to the Local Rademacher Complexity by finding an admissible range for one given the other. In addition, the Local VC-Entropy allows one to reduce the computational requirements that arise when dealing with the Local Rademacher Complexity in binary classification problems.
authors.affiliation: DIBRIS - University of Genoa, Via Opera Pia 13, I-16145 Genoa, Italy. Electronic address: Luca.Oneto@unige.it.
authors.forename: Luca
authors.initials: L
authors.lastname: Oneto
authors.affiliation: DIBRIS - University of Genoa, Via Opera Pia 13, I-16145 Genoa, Italy. Electronic address: Davide.Anguita@unige.it.
authors.forename: Davide
authors.initials: D
authors.lastname: Anguita
authors.affiliation: DITEN - University of Genoa, Via Opera Pia 11A, I-16145 Genoa, Italy. Electronic address: Sandro.Ridella@unige.it.
authors.forename: Sandro
authors.initials: S
authors.lastname: Ridella
mesh_terms: D019277:Entropy; D000069550:Machine Learning / Q000639:trends
keywords: Complexity measures; Generalization error bounds; Local Rademacher Complexity; Local Vapnik–Chervonenkis entropy; Statistical Learning Theory