Labeled sample compression schemes for complexes of oriented matroids

Abstract: The sample compression schemes were introduced by Littlestone and Warmuth in 1986 and have been vastly studied in the literature due to their importance in Machine Learning. Roughly speaking, the goal is to compress data as much as possible such that the original data can be reconstructed from the compressed data. The Vapnik-Chervonenkis dimension is central in Machine Learning and is important in Combinatorics and Discrete Geometry. Floyd and Warmuth in 1995 asked whether any set-family of VC-dimension $d$ has a sample compression scheme of size $O(d)$. This remains one of the oldest open problems in Machine Learning.

Recently we showed 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. 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.

In the talk, we will expalain COMs and the labeled sample compression scheme for them.

Based on the paper: V. Chepoi, K. Knauer, M. Philibert, Labeled sample compression schemes for complexes of oriented matroids, arXiv:2110.15168, 2021.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.