The VC dimension of k-fold union

DOI10.1016/J.IPL.2006.10.004zbMATH Open1185.68373OpenAlexW2017476151MaRDI QIDQ845927FDOQ845927

Authors: David Eisenstat, Dana Angluin 

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

combinatorial problemsVC dimensionconcept classesunions of conceptsintersections of concepts

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

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

Cited In (8)

• Boosting simple learners
• \(k\)-Fold unions of low-dimensional concept classes
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Differentially private learning of geometric concepts
• On the VC-dimension of uniform hypergraphs
• Tight lower bounds on the VC-dimension of geometric set systems
• Exploiting label dependencies for improved sample complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845927)