Labeled sample compression schemes for complexes of oriented matroids
This provides a theoretical advance in computational learning theory by generalizing compression schemes to broader combinatorial structures, though it appears incremental as it builds on prior work.
The paper tackles the problem of constructing labeled sample compression schemes for complexes of oriented matroids (COMs) with VC-dimension d, showing they admit a proper scheme of size d. This extends previous results and advances toward the sample compression conjecture in computational learning theory.
We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension $d$ admit a proper labeled sample compression scheme of size $d$. This considerably extends results of Moran and Warmuth on ample classes, of Ben-David and Litman on affine arrangements of hyperplanes, and of the authors on complexes of uniform oriented matroids, and is a step towards the sample compression conjecture -- one of the oldest open problems in computational learning theory. On the one hand, our approach exploits the rich combinatorial cell structure of COMs via oriented matroid theory. On the other hand, viewing tope graphs of COMs as partial cubes creates a fruitful link to metric graph theory.