Effective Littlestone Dimension

2024/11/22 by Valentino Delle Rose, Alexander Kozachinskiy, Rose, Valentino Delle +3 · 1 voice · 3 citations
Mathematics · #Advanced Topics in Algebra #cs.LG #cs.LO

paper · pdf · doi:10.48550/arxiv.2411.15109

openalex publication_date 2024/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one -- which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, finite effective Littlestone dimension also guarantees that the class consists only of computable functions.

Cited by

• Samplability makes learning easier
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
• Computable universal online learning

Discussions

• Preprint! This paper presents a surprising interplay between computability and combinatorial characterization of online learning in uniform mistake bound regime and it just got accepted to ALT 2025. # [bsky, 5 points, 1 comments]

Related

• Applications of Littlestone dimension to query learning and to compression
• Private PAC learning implies finite Littlestone dimension
• Resource-bounded Dimension in Computational Learning Theory
• Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
• Finite Littlestone Dimension Implies Finite Information Complexity