Unlabeled sample compression schemes and corner peelings for ample and maximum classes. (arXiv:1812.02099v2 [cs.DM] UPDATED)

We examine connections between combinatorial notions that arise in machine
learning and topological notions in cubical/simplicial geometry. These
connections enable to export results from geometry to machine learning. Our
first main result is based on a geometric construction by Tracy Hall (2004) of
a partial shelling of the cross-polytope which can not be extended. We use it
to derive a maximum class of VC dimension 3 that has no corners. This refutes
several previous works in machine learning from the …

arxiv compression