Applications of littlestone dimension to query learning and to compression
Abstract
In this paper we give several applications of Littlestone dimension. The first is to the model of Angluin and Dohrn [1], 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 [2] for Littlestone dimension.
Fields of Study & Subjects
Machine Learning and Algorithms
Computability
Logic
AI Algorithms
semigroups and automata theory
Publication details
- Journal / source
- Information and Computation
- Volume
- 309
- Pages
- 105424–105424
- Publication date
- 24 February 2026
- Language
- EN