2015/03/24 by Shay Moran, Moran, Shay, Amir Yehudayoff +1 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.LG
paper · pdf · doi:10.48550/arxiv.1503.06960
14 pages. The previous version of this text contained an error; Theorem 2.1 in it is false. This error only affects the statement for multi-labeled classes, and the construction for binary-labeled classes still holds. In the new version of the text, we added a relevant discussion in Section 4
openalex publication_date 2015/03/24 · arxiv created 2015/04/14 · arxiv updated 2015/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.