Labeled sample compression schemes for complexes of oriented matroids

10/28/2021
by   Victor Chepoi, et al.
0

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 and the authors and is a step towards the sample compression conjecture – one of the oldest open 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

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset