Applications of Littlestone dimension to query learning and to compression
This work addresses theoretical machine learning problems for researchers, but it is incremental as it builds on prior models and conjectures.
The paper tackles the problem of applying Littlestone dimension to query learning and compression, extending results for learning with equivalence queries and random counterexamples, and proving a strong version of a conjecture for Littlestone dimension in relation to extended d-compression schemes.
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.