Research map / Learning theory and algorithms / Sample complexity
Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Embed an intersection-closed class in a shortest-path-closed, intersection-closed extremal class | Intersection-closed concept classes · Concept classes of VC dimension d | unlabelled compression scheme size: at most 11d | Helped |
| Require an extremal class to contain a maximum subclass of VC dimension d-1 | Extremal classes · Extremal classes of VC dimension d | unlabelled compression scheme size: d | Helped |
| Choose a proper extremal subclass preserving an edge of every colour | Extremal classes · Extremal classes of VC dimension 2 | unlabelled compression scheme size: 2 | Helped |
| Add ordered shortest paths between comparable pairs while retaining intersection closure | Intersection-closed classes · Concept classes of VC dimension d | VC dimension of the closure: d to at most 11d | Mixed |
| Use a proper extremal subclass satisfying the cubical colour condition | Extremal classes · Extremal classes with a suitable subclass chain | unlabelled compression scheme size | Helped |
Closest papers by meaning
- Agnostic Sample Compression Schemes for Regression (ICML 2024 · similarity 0.88)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.85)
- Representation Preserving Multiclass Agnostic to Realizable Reduction (ICML 2025 · similarity 0.85)
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.84)
- The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm (NeurIPS 2026 · similarity 0.83)
- Transductive Learning is Compact (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.