DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.42

Applications of Littlestone Dimension to Query Learning and to Compression

Authors: Hunter Chase, James Freitag, and Lev Reyzin

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

In this paper we give several applications of Littlestone dimension. The first is to the model of [Angluin and Dohrn, 2017], where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend that model to infinite concept classes with an additional source of randomness. Third, we give improved results on the relationship of Littlestone dimension to classes with extended d-compression schemes, proving the analog of a conjecture of [Floyd and Warmuth, 1995] for Littlestone dimension.

Cite as

Hunter Chase, James Freitag, and Lev Reyzin. Applications of Littlestone Dimension to Query Learning and to Compression. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chase_et_al:LIPIcs.MFCS.2024.42,
  author =	{Chase, Hunter and Freitag, James and Reyzin, Lev},
  title =	{{Applications of Littlestone Dimension to Query Learning and to Compression}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{42:1--42:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.42},
  URN =		{urn:nbn:de:0030-drops-205988},
  doi =		{10.4230/LIPIcs.MFCS.2024.42},
  annote =	{Keywords: compression scheme, query learning, random queries, Littlestone dimension}
}

Search Results

Documents authored by Freitag, James

Applications of Littlestone Dimension to Query Learning and to Compression

Abstract

Cite as

Thanks for your feedback!

Could not send message