mlsanityData to 7 Oct 2026

Sample compression schemes for VC classes

arXiv 1503.06960 ↗First posted 24 Mar 2015cs.LGcited by 46

Not on the map. Why?

Abstract (arXiv)

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size k means that given an arbitrary list of labeled examples, one can retain only k of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class C with VC dimension d has a sample compression scheme of size exponential in d. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Mar 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 6; 2024: 10; 2025: 6; 2026: 8.

46 papers.

Sort:

  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  2. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  3. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  4. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  5. 2022Learning Losses for Strategic Classificationcited by 22
  6. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  7. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  8. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  9. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  10. 2024List Sample Compression and Uniform Convergencecited by 10
  11. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  12. 2022Adversarially Robust Learning with Tolerancecited by 9
34 more
  1. 2022Sample compression schemes for balls in graphscited by 8
  2. 2021Labeled sample compression schemes for complexes of oriented matroidscited by 7
  3. 2023Text Descriptions are Compressive and Invariant Representations for Visual Learningcited by 7
  4. 2024A Theory of Interpretable Approximationscited by 7
  5. 2021Primal and Dual Combinatorial Dimensionscited by 6
  6. 2023Multiclass Learnability Does Not Imply Sample Compressioncited by 6
  7. 2024A Characterization of List Regressioncited by 6
  8. 2022Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classescited by 5
  9. 2024Dual VC Dimension Obstructs Sample Compression by Embeddingscited by 5
  10. 2024Distribution Learnability and Robustnesscited by 4
  11. 2024Sample Compression Unleashed: New Generalization Bounds for Real Valued Lossescited by 4
  12. 2025Spherical dimensioncited by 4
  13. 2024Boosting, Voting Classifiers and Randomized Sample Compression Schemescited by 3
  14. 2024Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworkscited by 3
  15. 2023Applications of Littlestone dimension to query learning and to compressioncited by 2
  16. 2024Sample Compression Scheme Reductionscited by 2
  17. 2021VC dimension of partially quantized neural networks in the overparametrized regimecited by 1
  18. 2021Learning with distributional inverterscited by 1
  19. 2025Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphscited by 1
  20. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 1
  21. 2025The Parameterized Complexity of Computing the VC-Dimensioncited by 1
  22. 2026Sample-Near-Optimal Agnostic Boosting with Improved Running Timecited by 1
  23. 2026Learning Decision-Sufficient Representations for Linear Optimizationcited by 1
  24. 2026Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scalecited by 1
  25. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  26. 2021Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversioncited by 0
  27. 2022A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimensioncited by 0
  28. 2023Two Heads are Actually Better than One: Towards Better Adversarial Robustness via Transduction and Rejectioncited by 0
  29. 2025PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditionscited by 0
  30. 2025If generative AI is the answer, what is the question?cited by 0
  31. 2026Null Measurability at the Symmetrization Interface in VC Learningcited by 0
  32. 2026High-arity Sample Compressioncited by 0
  33. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0
  34. 2026An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimensioncited by 0