The VC dimension of k-fold union

DOI10.1016/J.IPL.2006.10.004MaRDI QIDQ845927zbMATH OpenOpenAlexFDO

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

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

Cited in

(8)

• \(k\)-Fold unions of low-dimensional concept classes
• Boosting simple learners
• 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
• Exploiting label dependencies for improved sample complexity
• Tight lower bounds on the VC-dimension of geometric set systems

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)