The VC dimension of \(k\)-fold union

DOI10.1016/j.ipl.2006.10.004zbMath1185.68373OpenAlexW2017476151MaRDI QIDQ845927

Dana Angluin, David Eisenstat

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.10.004

zbMATH Keywords

VC dimensioncombinatorial problemsconcept classesunions of conceptsintersections of concepts

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (6)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Exploiting label dependencies for improved sample complexity ⋮ Differentially Private Learning of Geometric Concepts ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ \(k\)-Fold unions of low-dimensional concept classes ⋮ Unnamed Item

Cites Work

• Learnability and the Vapnik-Chervonenkis dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: The VC dimension of \(k\)-fold union