Applications of Littlestone dimension to query learning and to compression

Autor:	Chase, Hunter, Freitag, James, Reyzin, Lev
Rok vydání:	2023
Předmět:	Computer Science - Machine Learning Mathematics - Logic
Druh dokumentu:	Working Paper
Popis:	In this paper we give several applications of Littlestone dimension. The first is to the model of \cite{angluin2017power}, 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 a strong version of a conjecture of \cite{floyd1995sample} for Littlestone dimension. Comment: arXiv admin note: substantial text overlap with arXiv:1904.10122
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2310.04812 Zobrazit plný text záznamu View this record from Arxiv