Unlabeled sample compression schemes and corner peelings for ample and maximum classes

  • 2018-12-05 16:42:48
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth
  • 1


We examine connections between combinatorial notions that arise in machinelearning and topological notions in cubical/simplicial geometry. Theseconnections 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. Thisrefutes several previous works in machine learning from the past 11 years. Inparticular, it implies that all previous constructions of optimal unlabeledsample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an unlabeled samplecompression scheme for maximum classes. We leave as open whether our unlabeledsample compression scheme extends to ample (a.k.a. lopsided or extremal)classes, which represent a natural and far-reaching generalization of maximumclasses. Towards resolving this question, we provide a geometriccharacterization in terms of unique sink orientations of the 1-skeletons ofassociated cubical complexes.


Introduction (beta)



Conclusion (beta)