Machine learning models that can explain their predictions using only a few training examples are likely to generalize well to new data. For decades, a central question has been whether every learnable binary classification problem, one where the data can be separated by a rule of a given complexity, can always be simplified to a small subset of its training examples. This is called the sample compression problem, and until now only an exponentially large simplification was known.
The authors prove that any binary classification problem whose complexity is measured by a quantity called VC dimension can be compressed using roughly the square of that dimension times a logarithmic factor. They construct a method that selects a small set of training examples and a short message, from which the labels of all original training examples can be recovered exactly.
This result resolves a thirty-year-old conjecture that polynomial-size compression is always possible. It provides a theoretical guarantee that Occam's razor, simpler explanations generalize better, applies universally to all learnable binary classification tasks, closing a major gap in learning theory.
