BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Victor Chepoi (Marseille)
DTSTART:20220316T160000Z
DTEND:20220316T170000Z
DTSTAMP:20260423T003248Z
UID:WCS/48
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/WCS/48/">Lab
 eled sample compression schemes for complexes of oriented matroids</a>\nby
  Victor Chepoi (Marseille) as part of Warwick Combinatorics Seminar\n\n\nA
 bstract\nThe sample compression schemes were introduced by Littlestone\nan
 d Warmuth in 1986 and have been\nvastly studied in the literature due to t
 heir importance in Machine\nLearning. Roughly speaking\, the goal\nis to c
 ompress data as much as possible such that the original data can\nbe recon
 structed\nfrom the compressed data.  The Vapnik-Chervonenkis dimension is 
 central\nin Machine Learning and  is\nimportant in Combinatorics and Discr
 ete Geometry. Floyd and Warmuth in\n1995 asked whether any set-family\nof 
 VC-dimension $d$ has a sample compression scheme of size $O(d)$. This\nrem
 ains one of the oldest open problems\nin Machine Learning.\n\nRecently we 
 showed that the topes of a complex of oriented matroids\n(abbreviated COM)
  of VC-dimension $d$ admit a proper labeled\nsample compression scheme of 
 size $d$. This considerably extends results\nof Moran and Warmuth and the 
 authors and is a step\ntowards the sample compression conjecture. On the o
 ne hand\, our approach\nexploits the rich combinatorial cell structure of 
 COMs\nvia oriented matroid theory. On the other hand viewing tope graphs o
 f\nCOMs as partial cubes creates a fruitful link to metric graph theory.\n
 \nIn the talk\, we will expalain COMs and the labeled sample compression\n
 scheme for them.\n\nBased on the paper:\nV. Chepoi\, K. Knauer\, M. Philib
 ert\, Labeled sample compression schemes\nfor complexes of oriented matroi
 ds\, arXiv:2110.15168\, 2021.\n
LOCATION:https://researchseminars.org/talk/WCS/48/
END:VEVENT
END:VCALENDAR