Search Results

Documents authored by Warmuth, Manfred K.

Found 2 Possible Name Variants:

Warmuth, Manfred K.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.34
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes

Authors: Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
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 H. 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 past 11 years. In particular, it implies that the previous constructions of optimal unlabeled compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an optimal unlabeled compression scheme for maximum classes. We leave as open whether our unlabeled compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes.
Cite as

Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.ICALP.2019.34,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Moran, Shay and Warmuth, Manfred K.},
  title =	{{Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.34},
  URN =		{urn:nbn:de:0030-drops-106105},
  doi =		{10.4230/LIPIcs.ICALP.2019.34},
  annote =	{Keywords: VC-dimension, sample compression, Sauer-Shelah-Perles lemma, Sandwich lemma, maximum class, ample/extremal class, corner peeling, unique sink orientation}
}

Warmuth, Manfred

Document
DOI: 10.4230/DagSemRep.91
Theory and Praxis of Machine Learning (Dagstuhl Seminar 9426)

Authors: Thomas Dietterich, Wolfgang Maass, Hans-Ulrich Simon, and Manfred Warmuth

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Thomas Dietterich, Wolfgang Maass, Hans-Ulrich Simon, and Manfred Warmuth. Theory and Praxis of Machine Learning (Dagstuhl Seminar 9426). Dagstuhl Seminar Report 91, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)

Copy BibTex To Clipboard

@TechReport{dietterich_et_al:DagSemRep.91,
  author =	{Dietterich, Thomas and Maass, Wolfgang and Simon, Hans-Ulrich and Warmuth, Manfred},
  title =	{{Theory and Praxis of Machine Learning (Dagstuhl Seminar 9426)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{91},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.91},
  URN =		{urn:nbn:de:0030-drops-149796},
  doi =		{10.4230/DagSemRep.91},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact