2026-07-23T01:41:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20598 2024-08-26T11:40:47Z ddc:004 open_access

Applications of Littlestone Dimension to Query Learning and to Compression Chase, Hunter Freitag, James Reyzin, Lev compression scheme query learning random queries Littlestone dimension 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hunter Chase and James Freitag and Lev Reyzin 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.42 urn:nbn:de:0030-drops-205988 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.42 eng https://creativecommons.org/licenses/by/4.0/legalcode