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 problemsconcept classesintersections of conceptsunions of conceptsVC dimension

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

(11)

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

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)