Teaching and Compressing for Low VC-Dimension
From MaRDI portal
Publication:4604393
DOI10.1007/978-3-319-44479-6_26zbMath1425.68352arXiv1502.06187OpenAlexW2962808814MaRDI QIDQ4604393
Shay Moran, Avi Wigderson, Amir Shpilka, Amir Yehudayoff
Publication date: 26 February 2018
Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.06187
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items (4)
A note on hardness of computing recursive teaching dimension ⋮ The VC-dimension of axis-parallel boxes on the torus ⋮ Labeled Compression Schemes for Extremal Classes ⋮ On Version Space Compression
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Population recovery and partial identification
- Algebraic methods proving Sauer's bound for teaching complexity
- Teachability in computational learning
- Teaching a smarter learner.
- \(\epsilon\)-nets and simplex range queries
- Occam's razor
- Inferring decision trees using the minimum description length principle
- Central limit theorems for empirical measures
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Learning from different teachers
- Density and dimension
- On the complexity of teaching
- On weak learning
- Boosting a weak learning algorithm by majority
- Externally definable sets and dependent pairs
- Shifting: one-inclusion mistake bounds and sample compression
- On the density of families of sets
- Restriction access
- Learning Binary Relations and Total Orders
- Sample Compression Schemes for VC Classes
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Learning Integer Lattices
- 10.1162/jmlr.2003.3.4-5.723
- Recursive Teaching Dimension, Learning Complexity, and Maximum Classes
- A Geometric Approach to Sample Compression
- Teaching Dimension and the Complexity of Active Learning
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Teaching and Compressing for Low VC-Dimension
